The final bottleneck in our program is the lazy list itself. While
we can avoid allocating it all at once, there is still memory traffic
each time around the loop, as we demand the next cons cell in the list,
allocate it to the heap, operate on it, and continue. The list type is
also polymorphic, so the elements of the list will be represented as
What we’d like to do is eliminate the list entirely, keeping just the next element we need in a register. Perhaps surprisingly, GHC is able to transform the list program into a listless version, using an optimization known as deforestation, which refers to a general class of optimizations that involve eliminating intermediate data structures. Due to the absence of side effects, a Haskell compiler can be extremely aggressive when rearranging code, reordering and transforming wholesale at times. The specific deforestation optimization we will use here is stream fusion.
This optimization transforms recursive
list generation and transformation functions into nonrecursive
unfolds. When an
unfold appears next to a
fold, the structure between them is then eliminated entirely,
yielding a single, tight loop with no heap allocation. The optimization
isn’t enabled by default, and it can radically change the complexity of
a piece of code, but it is enabled by a number of data structure
libraries, which provide rewrite rules, custom optimizations, that the compiler applies to functions that the ...