Call-pattern specialisation for Haskell programs

Submitted to ICFP 2007

User-defined data types, pattern-matching, and recursion are ubiquitous features of Haskell programs. Sometimes a function is called with arguments that are statically known to already be in constructor form, so that the work of pattern-matching is wasted. Even worse, the argument is sometimes freshly-allocated, only to be immediately decomposed by the function.

In this paper we describe a simple, modular transformation that specialises recursive functions according to their argument “shapes”. We show that such a transformation has a simple, modular implementation, and that it can be extremely effective in practice, eliminating both pattern-matching and heap allocation. We describe our implementation of this constructor specialisation transformation in the Glasgow Haskell Compiler, and give measurements of its effectiveness.

See also “Stream Fusion From Lists to Streams to Nothing at All” by Coutts, Leshchinskiy, and Stewart.