Stream Fusion: From Lists to Streams to Nothing at All
In ICFP '07: Proceedings of the 2007 ACM SIGPLAN International Conference on Functional Programming, pp. 315-326, ACM, New York, NY, USA.
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.
See also Don's stream fusion page.