Monadic fold, Monadic build, Monadic 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: Abstract: Short cut fusion improves the efficiency of modularly constructed programs by eliminating intermediate data structures produced by one program component and immediately consumed by another. We define a combinator which expresses uniform production of data structures in monadic contexts, and is the natural counterpart to the well-known monadic fold which consumes them. Like the monadic fold, our new combinator quantifies over monadic algebras rather than standard ones. Together with the monadic fold, it gives rise to a new short cut fusion rule for eliminating intermediate data structures in monadic contexts. This new rule differs significantly from previous short cut fusion rules, all of which are based on combinators which quantify over standard, rather than monadic, algebras. We give examples illustrating the benefits of quantifying over monadic algebras, prove our new fusion rule correct, and show how it can improve programs. We also consider its coalgebraic dual.

Additional Information

Patricia Johann and Neil Ghani (2009) "Monadic fold, Monadic build, Monadic Short Cut Fusion". Proceedings, Symposium on Trends in Functional Programming 2009 (TFP'09), pp. 9 - 23. Version Of Record Available At
Language: English
Date: 2009
monads, fusion, algebraic structures, monadic fold, monadic algebra

Email this document to