Monadic fold, Monadic build, Monadic Short Cut Fusion

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