Lazy data structures require allocation. GHC's lists use build/fold fusion to remove intermediate lists but that's basically just a less reliable way of convert

Lazy data structures require allocation. GHC's lists use build/fold fusion to remove intermediate lists but that's basically just a less reliable way of converting to folds http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Base.html#build http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GH... The other common fusion technique used in haskell is stream fusion which is very similar to the mutual-recursion-encoded-as-sum-type version in the blog post. There is also indexing-based fusion which the Repa library uses. It allows more control over traversal order (think optimizing stencil codes) but requires regular arrays, e.g. no filtering. There are some other research projects like specialized compiler passes via hermit but afaik nothing really production ready.