Publications

• Stream Fusion: From Lists to Streams to Nothing at All Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007.

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.

• Rewriting Haskell Strings Duncan Coutts, Roman Leshchinskiy and Don Stewart. PADL 2007.

Awarded "Most Practical Paper" at PADL.

The Haskell String type is notoriously inefficient. We introduce a new data type, ByteString, based on lazy lists of byte arrays, combining the speed benefits of strict arrays with lazy evaluation. Equational transformations based on term rewriting are used to deforest intermediate ByteStrings automatically. We describe novel fusion combinators with improved expressivity and performance over previous functional array fusion strategies. A library for ByteStrings is implemented, providing a purely functional interface, and approaches the speed of low-level mutable arrays in C.

I also have a couple presentations on this topic: one on the ByteString type and another on the fusion system and its application to the ByteString type.

Unpublished reports and talks

• (Oct 2004) a dissertation reporting on my first year's research and setting out the topic and a plan for the final PhD thesis.
• (Sep 2004) a summary paper and slides from my talk at the Student Conference about partial evaluation for Haskell.
• (Dec 2003) slides from a Cakes talk on building recursive data structures in Haskell.
• (Aug 2002) slides and an accompanying paper presented at the participants' session of the 2002 Advanced Functional Programming Summer School on an arrow style combinator for structuring computations that collect and report errors.