In the theory of programming languages in computer science, deforestation (also known as fusion) is a program transformation to eliminate intermediate lists or tree structures that are created and then immediately consumed by a program.
The term "deforestation" was originally coined by Philip Wadler in his 1990 paper "Deforestation: transforming programs to eliminate trees".
Deforestation is typically applied to programs in functional programming languages, particularly non-strict programming languages such as Haskell. One particular algorithm for deforestation, shortcut deforestation, is implemented in the Glasgow Haskell Compiler. Deforestation is closely related to escape analysis.
See also
References
Wadler, Philip (1990). "Deforestation: transforming programs to eliminate trees". Theoretical Computer Science. 73 (2): 231–248. doi:10.1016/0304-3975(90)90147-A. http://homepages.inf.ed.ac.uk/wadler/papers/deforest/deforest.ps ↩
Gill, Andrew; John Launchbury; Simon Peyton Jones (1993). "A short cut to deforestation" (PDF). Proc. Conf. on Functional Programming Languages and Computer Architecture. pp. 223–232. doi:10.1145/165180.165214. http://research.microsoft.com/en-us/um/people/simonpj/papers/deforestation-short-cut.pdf ↩
Peyton Jones, Simon; Andrew Tolmach; C.A.R. Hoare (2001). "Playing by the rules: rewriting as a practical optimization technique in GHC" (PDF). Proc. ACM/SIGPLAN Haskell Workshop. https://www.microsoft.com/en-us/research/wp-content/uploads/2001/09/rules.pdf ↩