Skip to main content

Theory and Practice of Fusion

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

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 tech­niques. 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.

Book Title
Pre−proceedings of the 22nd Symposium on the Implementation and Application of Functional Languages
Editor
Hage‚ Jurriaan
Location
Alphen aan den Rijn‚ The Netherlands
Month
August
Note
The pre−proceedings appeared as Utrecht University Technical Report UU−CS−2010−020: http://www.cs.uu.nl/research/techreps/repo/CS-2010/2010-020.pdf
Pages
402–421
Series
IFL '10
Year
2010