Deforestation is a ProgramTransformation that eliminates intermediate data-structures (trees). The technique was invented by PhilipWadler for optimization of functional programs.

CategoryOptimization

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

CategoryOptimization

Revision: r1.3 - 04 Dec 2001 - 10:45 - EelcoVisser

Copyright © 1999-2020 by the contributing authors.
All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback