Theory and Practice of Fusion

Ralf Hinze, Thomas Harper and Daniel W. H. James

Pre-symposium Proceedings of IFL ’10, Sept. 1–3, 2010, Alphen aan den Rijn, The Netherlands
PDF | BibTEX
Post-symposium Proceedings of IFL ’10
PDF | DOI | BibTEX
Technical Report
PDF | BibTEX

Abstract

There are a number of approaches for eliminating intermediate data structures in functional programs—this elimination is com­monly known as fusion. Existing fusion strategies are built upon var­ious, but related, recursion schemes, such as folds and unfolds. We use the concept of recursive coalgebras as a unifying theoretical and notational framework to explore the foundations of these fusion tech­niques. We first introduce the calculational properties of recur­sive coalgebras and demonstrate their use with proofs and deriv­ations in a calculational style, then provide an overview of fusion tech­niques by bringing them together in this setting. We also show­case these developments with examples in Haskell.

Keywords

shortcut fusion, initial algebras, final coalgebras, hylomorphisms, recursive coalgebras, acid rain rule, foldr/build, destroy/unfoldr, stream fusion