Fold Fusion and the Elimination of Intermediate Lists

Composing two list functions allocates a list that exists only to be consumed. map f (map g xs) builds an intermediate list of the same length as the input and immediately discards it, so the program does twice the traversal and allocates one cons cell per element for nothing. The obvious fix is to write the composition by hand, and the interesting question is whether the compiler can do it instead, reliably, without changing the meaning of programs that share the intermediate structure.

The shape of the waste

A cons cell in GHC’s heap is two machine words, a pointer to the head and a pointer to the tail, and a cons cell with an evaluated head and tail therefore occupies those 16 bytes on a 64-bit machine before the boxed elements are counted. A list of n integers costs roughly 16n bytes for the spine plus whatever the boxed integers themselves occupy. Each stage of a chain allocates one such list, so three stages retain one intermediate list at a time and allocate three, and the peak residency is proportional to n and the allocation rate to 3n.

The traversal count is the other half. Each stage walks the spine, so k stages cost k traversals. Neither cost is asymptotically worse than the fused version; both are constant-factor losses that scale with the length of the chain and the size of the elements. The reason fusion matters is that these constants are large in exactly the code where lists are the natural idiom: parsing, transformation, and serialization chains are typically several stages long.

The foldr/build rule

The fusion rule rests on a representation trick. A list producer is written not as a list but as a function that consumes the two constructors:

build :: (forall b. (a -> b -> b) -> b -> b) -> [a]
build g = g (:) []

map' :: (a -> b) -> [a] -> [b]
map' f xs = build (\c n -> foldr (\x acc -> c (f x) acc) n xs)

build applies its argument to the real constructors, so the resulting list is ordinary. The point of the wrapping is that a consumer written with foldr can be applied to g directly, without build ever running:

foldr k z (build g)  =  g k z

Read left to right, this is the fusion rule. The left side allocates the list that build would produce and then folds it; the right side substitutes the consumer’s k and z into the producer’s function, so the producer builds its result directly in the consumer’s algebra. No list exists at any point. map' f composed with sum becomes foldr (\x acc -> (f x) + acc) 0 xs, one traversal, zero cons cells.

The rule is a compiler rewrite, not a source-level transformation. GHC implements it as a RULES pragma attached to build, with the constraint that g must be a syntactic argument so that the rule can fire during inlining. A producer that is not written with build does not fuse, which is why the list functions in base are written in this style: map, filter, take, iterate, and the enumFromTo enumeration are defined with build so that they fuse with a foldr-shaped consumer.

Why the rule is semantically safe

The equation foldr k z (build g) = g k z is not a heuristic. It follows from the parametric type of g: forall b. (a -> b -> b) -> b -> b. By the free theorem for that type, g must be a homomorphism between list algebras, so applying it to (:) and [] and then folding with k and z is the same as applying it to k and z directly. The type is what licenses the rewrite; a function of a less polymorphic type would not satisfy the equation.

This is also why user-written rules are dangerous. A rule is a promise that two expressions are equal for all instantiations, and the compiler will apply it wherever the pattern matches. A rule whose left side is more general than its right side, or whose right side duplicates a variable that appears once on the left, changes the number of evaluations of that expression. Under a lazy language the change is invisible for pure expressions and visible when the expression diverges; under a strict one it is visible for any expression with an effect.

Where fusion fails: seq, sharing, and arity

Three conditions defeat the rule, and each is a real limitation rather than a compiler bug.

Strictness. The equation above holds in a language where foldr k z (build g) and g k z have the same value for every k, z, g. It does not hold when seq can observe the intermediate list. A seq placed on the list argument of the left side forces the spine that build produced; the fused right side never produces that spine, so the same seq forces a different expression or nothing at all. The rule is therefore not valid in the presence of seq, and the practical consequence is that a program relying on seq to control the evaluation of an intermediate list may reach a different ⊥ after fusion. The difference is not a bug in the program’s logic; it is a difference in which of two expressions was demanded first.

Sharing. If the intermediate list is used twice, fusion cannot eliminate it, because the two consumers would each have to re-run the producer. A compiler that fuses in that situation duplicates the producer’s work, which is a pessimization, and one that refuses to fuse leaves the allocation. GHC’s rules carry phase annotations so that build is inlined only at a use site where the rewrite will fire, which is what keeps the duplication out of programs that share a list. A binding whose result is used in two places keeps its list, and the programmer who wants the fused version has to restructure the code so the shared value is something cheaper than a list.

Arity and inlining. The rule fires only after build has been inlined at the use site, which requires the producer to be small enough for the inliner and the consumer to be visible in the same module or to have an unfolding exported across modules. A producer in a separately compiled module that does not export an unfolding cannot fuse, and the fix is an INLINABLE pragma. A producer behind a class method dispatch may not fuse at all, because the dictionary indirection hides the call. These are engineering constraints of the optimizer rather than properties of the calculus, and they mean that fusion’s benefit is uneven across a codebase.

Deforestation, and why the general version lost

Wadler’s deforestation applies the same idea to arbitrary trees. The algorithm repeatedly applies rewrites that push a consumer into a producer, so that a tree built by one function and consumed by another never materializes. It is a general-purpose transformation on a first-order functional language, and it subsumes the list case.

The reason it is not what compilers use is cost and predictability. Deforestation needs to analyse the whole program to find producer-consumer pairs, it can duplicate work when it fuses a shared structure, and its termination is not obvious: a rewrite that pushes a consumer inward can create new opportunities indefinitely. Wadler’s formulation handles termination with a careful measure, and the implementation still has to decide when to stop. A single hand-written rule for the list type is cheaper to implement, easier to verify, and covers the compositions that matter in practice.

The successor in GHC is a family of rules rather than one. foldr/build covers foldr-shaped consumers; augment covers producers that append onto an existing accumulator, with matching foldr/augment and foldl/augment rules so that a fold can build its elements directly in the consumer’s algebra. The union of the rules covers more programs than any single rule, at the cost of more rules that can interact badly with each other and with user-supplied rules.

The cost when it works, and the cost when it does not

When fusion fires, a three-stage chain becomes one loop. The allocation of the intermediate lists goes to zero, the traversal count goes from three to one, and the resulting code is the hand-written loop that a programmer would have written in a strict language. The transformation is purely local after inlining, so the risk is bounded: the worst case is code that does not fuse and behaves as before.

When it does not fire, the program is exactly the unfused program, and the only cost is a missed opportunity. The failure is silent: nothing warns that a chain allocated two lists. A programmer who wants to know has to read the optimizer’s output, and the shape of the output depends on inlining decisions that change between compiler versions.

There is a third case, which is the one that causes trouble: fusion fires but changes the program’s behaviour under seq. The rule is stated for a language in which foldr k z (build g) and g k z have the same value for every k, z, and g, and the equation can fail once seq can observe the half-built list, because the left side has a spine to force and the right side has none. A program that used seq on an intermediate list to decide when the producer’s elements were computed can therefore compute a different expression once the list is gone. The change is in which intermediates are demanded, not in the value produced, which is why a rewrite that is sound for values is not automatically sound for demand.

The right way to read fusion is therefore as a rewrite that is sound for values and not for evaluation order. The universal property of fold supplies the equation; the compiler supplies the mechanism; and seq, sharing, and inlining decide whether the mechanism applies. Programs that need a specific evaluation order should say so with strictness annotations rather than rely on an intermediate list to impose it, and programs that need a specific allocation profile should be written with the fused shape directly rather than hoped for.

For types other than lists the same transformation is expressed as a fusion law between a catamorphism and an anamorphism, where a producer-consumer pair collapses into a single hylomorphism. That generalization is where the list-specific rules come from, and it is also where the termination argument becomes hard.