Theory and Practice of Fusion
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
commonly known as fusion. Existing fusion strategies are built upon
various, 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
techniques. We first introduce the calculational properties of
recursive coalgebras and demonstrate their use with proofs and
derivations in a calculational style, then provide an overview of fusion
techniques by bringing them together in this setting. We also
showcase 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