Removing intermediate data structures with stream fusion

Tom Harper ( OUCL )

Fusion is a set of techniques that use program transformations to remove intermediate data structures. A set of fusion techniques called "short cut" fusion have been used in Haskell that use simple rewrite rules to accomplish fusion over lists and other data structures. One technique in particular, stream fusion, has been able to fuse a wide range of functions and has been used successfully to fuse lists and arrays for various applications.

In this talk, I will provide a brief overview of short cut fusion, and compare stream fusion to other well-known fusion techniques. I will also present some libraries that currently implement stream fusion, including a comparison of lists with Haskell's current list fusion framework.