Lambda the Ultimate

In functional programming, programs are often written in a compositional style. There are many advantages to this, such as clarity and modularity, but the resulting programs can be inefficient in terms of space, due to the use of intermediate data structures. These structures may be removed using deforestation techniques, but whether the space performance is actually improved depends on the structures being consumed in the same order that they are produced. In this paper we explore this problem and suggest a solution, in particular for lists and then generalising to trees.

Since the paper discusses many examples, it is quite enjoyable to read and can even serve as an introduction to folds.