[Solved]: How does 'deforestation' remove 'trees' from a program?

Problem Detail: 

I think understand how deforestation consumes and produces a list at the same time (from a fold and an unfold function -- see this good answer on CodeReview here), but when I compared that with the wikipedia entry on the technique it talked about 'removing trees' from a program.

I understand how a program can be parsed into a syntactic parse tree (is that right?), but what is the meaning of this use of deforestation for some kind of simplification (is it?) of programs? And how would I do it to my code?

Asked By : Cris Stringfellow

Answered By : cody

Yatima2975 seems to have covered your first two questions, I'll try to cover the third. To do this I'll treat an unrealistically simple case, but I'm sure you'll be able to imagine something more realistic.

Imagine you want to compute the depth of the full binary tree of order $n$. The type of (unlabeled) binary trees is (in Haskell syntax):

type Tree = Leaf | Node Tree Tree 

Now the full tree of order $n$ is:

full : Int -> Tree full n | n == 0 = Leaf full n = Node (full (n-1)) (full (n-1)) 

And the depth of a tree is computed by

depth : Tree -> Int depth Leaf = 0 depth (Node t1 t2) = 1 + max (depth t1) (depth t2) 

Now you can see that any computation of $\mathrm{depth}\ (\mathrm{full}\ n)$ will first construct the full tree of order $n$ using $\mathrm{full}$ and then deconstruct that tree using $\mathrm{depth}$. Deforestation relies on the observation that such a pattern (construction followed by deconstruction) can often be short-circuited: we can replace any calls to $\mathrm{depth}\ (\mathrm{full}\ n)$ by a single call to $\mathrm{full\_depth}$:

full_depth : Int -> Int full_depth n | n == 0 = 0 full_depth n = 1 + max (full_depth (n-1)) (full_depth (n-1)) 

This avoids memory allocation of the full tree, and the need to perform pattern matching, which greatly improves performance. In addition, if you add the optimization

max t t --> t 

Then you have turned an exponential time procedure into a linear time one... It would be cool if there was an additional optimization that recognized that $\mathrm{full\_depth}$ was the identity on integers, but I am not sure that any such optimization is used in practice.

The only mainstream compiler that performs automatic deforestation is GHC, and if I recall correctly, this is performed only when composing built-in functions (for technical reasons).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10129