Deforestation (computer science)

In the theory of programming languages in computer science, deforestation (also known as fusion) is a program transformation to eliminate tree structures.

The term "deforestation" was originally coined by Philip Wadler in his paper "Deforestation: transforming programs to eliminate trees".^[1]

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,^[2] is implemented in the Glasgow Haskell Compiler.^[3]

References

This programming-language-related article is a stub. You can help Wikipedia by expanding it.

v t e Compiler optimizations
Basic block	Peephole optimization
Loop optimization	Induction variable Strength reduction Loop fusion Loop inversion Loop interchange Loop-invariant code motion Loop nest optimization Loop unrolling Loop splitting Loop unswitching Software pipelining Automatic parallelization
Data-flow analysis	Common subexpression elimination Constant folding Induction variable recognition and elimination Dead store elimination Use-define chain Live variable analysis Available expression
SSA-based	Global value numbering Sparse conditional constant propagation
Code generation	Register allocation Instruction selection Instruction scheduling Rematerialization
Functional	Removing recursion Deforestation
Global	Interprocedural optimization
Other	Bounds-checking elimination Dead code elimination Inline expansion Jump threading
Static analysis	Alias analysis Pointer analysis Shape analysis Escape analysis Array access analysis Dependence analysis Control flow analysis Data flow analysis