Monadic augment and generalised short cut fusion Export

@inproceedings{citeulike:333545, abstract = {Monads are commonplace programming devices that are used to uniformly structure computations with effects such as state, exceptions, and I/O. This paper further develops the monadic programming paradigm by investigating the extent to which monadic computations can be optimised by using generalisations of short cut fusion to eliminate monadic structures whose sole purpose is to "glue together" monadic program components.We make several contributions. First, we show that every inductive type has an associated build combinator and an associated short cut fusion rule. Second, we introduce the notion of an inductive monad to describe those monads that give rise to inductive types, and we give examples of such monads which are widely used in functional programming. Third, we generalise the standard augment combinators and cata/augment fusion rules for algebraic data types to types induced by inductive monads. This allows us to give the first cata/augment rules for some common data types, such as rose trees. Fourth, we demonstrate the practical applicability of our generalisations by providing Haskell implementations for all concepts and examples in the paper. Finally, we offer deep theoretical insights by showing that the augment combinators are monadic in nature, and thus that our cata/build and cata/augment rules are arguably the best generally applicable fusion rules obtainable.}, address = {New York, NY, USA}, author = {Ghani, Neil and Johann, Patricia and Uustalu, Tarmo and Vene, Varmo}, booktitle = {ICFP '05: Proceedings of the tenth ACM SIGPLAN international conference on Functional programming}, citeulike-article-id = {333545}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1086365.1086403}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1086365.1086403}, doi = {10.1145/1086365.1086403}, isbn = {1595930647}, keywords = {category-theory, functional-programming, generic-programming, haskell, monads, optimization, polymorphism, program-transformation, rank-2, shortcut-deforestation, type-classes, types}, pages = {294--305}, posted-at = {2005-09-28 09:56:19}, priority = {0}, publisher = {ACM Press}, title = {Monadic augment and generalised short cut fusion}, url = {http://dx.doi.org/10.1145/1086365.1086403}, year = {2005} }

TY - CONF ID - citeulike:333545 L3 - citeulike-article-id:333545 N2 - Monads are commonplace programming devices that are used to uniformly structure computations with effects such as state, exceptions, and I/O. This paper further develops the monadic programming paradigm by investigating the extent to which monadic computations can be optimised by using generalisations of short cut fusion to eliminate monadic structures whose sole purpose is to "glue together" monadic program components.We make several contributions. First, we show that every inductive type has an associated build combinator and an associated short cut fusion rule. Second, we introduce the notion of an inductive monad to describe those monads that give rise to inductive types, and we give examples of such monads which are widely used in functional programming. Third, we generalise the standard augment combinators and cata/augment fusion rules for algebraic data types to types induced by inductive monads. This allows us to give the first cata/augment rules for some common data types, such as rose trees. Fourth, we demonstrate the practical applicability of our generalisations by providing Haskell implementations for all concepts and examples in the paper. Finally, we offer deep theoretical insights by showing that the augment combinators are monadic in nature, and thus that our cata/build and cata/augment rules are arguably the best generally applicable fusion rules obtainable. SN - 1595930647 AD - New York, NY, USA EP - 305 TI - Monadic augment and generalised short cut fusion PB - ACM Press T2 - ICFP '05: Proceedings of the tenth ACM SIGPLAN international conference on Functional programming SP - 294 KW - category-theory KW - functional-programming KW - generic-programming KW - haskell KW - monads KW - optimization KW - polymorphism KW - program-transformation KW - rank-2 KW - shortcut-deforestation KW - type-classes KW - types AU - Ghani, Neil AU - Johann, Patricia AU - Uustalu, Tarmo AU - Vene, Varmo PY - 2005/// UR - http://dx.doi.org/10.1145/1086365.1086403 ER -