Monadic Augment And Generalized Short Cut Fusion

ASU Author/Contributor (non-ASU co-authors, if there are any, appear on document)
Patricia Johann Ph.D, Professor (Creator)
Appalachian State University (ASU )
Web Site:

Abstract: Monads are commonplace programming devices that are used to uniformly structure computations;in particular, they are often used to mimic the effects of impure features suchas state, error handling, and I/O. This paper further develops the monadic programmingparadigm by investigating the extent to which monadic computations can be optimisedby using generalisations of short cut fusion to eliminate monadic structures whose solepurpose is to \glue together" monadic program components.Ghani, Uustalu, and Vene have recently shown that every inductive type has an associatedbuild combinator and an associated short cut fusion rule. They have also used thenotion of a parameterised monad to describe those monads that give rise to inductive types,and have shown that the standard augment combinators and cata/augment fusion rulesfor algebraic data types can be generalised to xed points of all parameterised monads.We revisit these augment combinators and generalised short cut fusion rules for such typesbut consider them from a functional programming perspective, rather than a categoricalone. In addition to making the category-theoretic ideas of Ghani, Uustalu, and Venemore easily accessible to a wider audience of functional programmers, we demonstratetheir practical applicability by developing nontrivial application programs and performingmodest benchmarking on them. We also show how the cata/augment rules can serve asthe basis for deriving additional generic fusion laws, thus opening the way for an algebraof fusion. Finally, we o er deep theoretical insights, arguing that the augment combinatorsare monadic in nature, and thus that the cata/build and cata/augment rules arearguably the best generally applicable fusion rules obtainable.

Additional Information

Ghani, Neil; Johann, Patricia. (2007) Monadic Augment and Generalized Short Cut Fusion. Journal of Functional Programming, vol. 17, no. 6 (2007), pp. 731 - 776. (ISSN: 0956-7968) [doi: 10.1017/ S0956796807006314] Version of Record Available From
Language: English
Date: 2007
monadic, augment, fusion

Email this document to