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 
<verbatim>
  h(x) = f(g(x))
</verbatim>
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