Stream Fusion

[ICFP Submission - Referees skip this]
Stream Fusion: From Lists to Streams to Nothing at All applies the fusion system from Rewriting Haskell Strings to ordinary lists. The result is more comprehensive than earlier systems like foldr/build.

This paper presents an automatic fusion system, stream fusion, based on equational transformations, that fuses a wider range of functions than existing short-cut fusion systems. In particular, stream fusion is able to fuse zips, left folds and functions over nested lists, including list comprehensions. A distinguishing feature of the stream fusion framework is its simplicity: by transforming list functions to expose their structure, intermediate values are eliminated by general purpose compiler optimisations.

We have reimplemented the entire Haskell standard list library on top of our framework, providing stream fusion for Haskell lists. By allowing a wider range of functions to fuse, we see an increase in the number of occurrences of fusion in typical Haskell programs. We present benchmarks documenting time and space improvements.

Darius Bacon suggests the SERIES package for common lisp may be related.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


The authors are Duncan Coutts, Roman Leshchinskiy and Don Stewart, the same group responsible for Rewriting Haskell Strings.

SML translation

I made a translation of the stream fusion technique to SML. See here. Of course, one can't simply reimplement the list datatype of SML using the technique, but streams can be useful in SML programming as such.