Program-Transformation.Org: The Program Transformation Wiki

Deforestation is a ProgramTransformation that eliminates intermediate data-structures (trees). The technique was invented by PhilipWadler for optimization of functional programs.
The idea is to fuse the composition of two functions `f(g(x))`

into a new function `h(x)`

such that the data-structure that is passed from `g`

to `f`

is never constructed. This is achieved by creating
a new function

h(x) = f(g(x))and inlining the definitions of

`f`

and `g`

. If everything works out the data deconstructors of `f`

can be fused with the data constructors of `g`

and no data are constructed.
Recursive invocations `f(g(y))`

of the fused functions can be replaced with a call to the new function `h(y)`

.
Algorithms for deforestation

-- EelcoVisser - 02 Dec 2001