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
* ShortCutFusion
* WarmFusion
-- Main.EelcoVisser - 02 Dec 2001
-----
CategoryOptimization