# How does 'deforestation' remove 'trees' from a program?

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?

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).

• Awarded because I got more out this answer from the way it was formulated than from the other answers, even though they essentially cover the same territory. – Cris Stringfellow Mar 2 '13 at 12:44

First, lists are a kind of trees. If we represent a list as a linked list, it's just a tree whose each node has either 1 or 0 descendants.

Parse trees are just an utilization of trees as a data structure. Trees have many many applications in computer science, including sorting, implementing maps, associative arrays, etc.

In general, list, trees etc. are recursive data structures: Each node contains some information and another instance of the same data structure. Folding is an operation over all such structures that recursively transforms nodes to values "bottom up". Unfolding is the reverse process, it converts values to nodes "top down".

For a given data structure, we can mechanically construct their folding and unfolding functions.

As an example, let's take lists. (I'll use Haskell for the examples as it's typed and its syntax is very clean.) List is either an end or a value and a "tail".

data List a = Nil | Cons a (List a)


Now let's imagine we're folding a list. At each step, we have the current node to be folded and we have already folded its recursive sub-nodes. We can represent this state as

data ListF a r = NilF | ConsF a r


where r is the intermediate value constructed by folding the sublist. This allows us to express a folding function over lists:

foldList :: (ListF a r -> r) -> List a -> r
foldList f Nil            = f NilF
foldList f (Cons x xs)    = f (ConsF x (foldList f xs))


We convert List into ListF by recursively folding over its sublist and then use a function defined on ListF. If you think about it, this is just another representation of standard foldr:

foldr :: (a -> r -> r) -> r -> List a -> r
foldr f z = foldList g
where
g NilF          = z
g (ConsF x r)   = f x r


We can construct unfoldList in the same fashion:

unfoldList :: (r -> ListF a r) -> r -> List a
unfoldList f r = case f r of
NilF        -> Nil
ConsF x r'  -> Cons x (unfoldList f r')


Again, it's just another representation of unfoldr:

unfoldr :: (r -> Maybe (a, r)) -> r -> [a]


(Notice that Maybe (a, r) is isomorphic to ListF a r.)

And we can construct a deforestation function too:

deforest :: (ListF a r -> r) -> (s -> ListF a s) -> s -> r
deforest f u s = f (map (deforest f u) (u s))
where
map h NilF        = NilF
map h (ConsF x r) = ConsF x (h r)


It simply leaves out the intermediate List and fuses the folding and unfolding functions together.

The same procedure can be applied to any recursive data structure. For example, a tree whose nodes can have 0, 1, 2 or descendants with values on 1- or 0-branching nodes:

data Tree a = Bin (Tree a) (Tree a) | Un a (Tree a) | Leaf a

data TreeF a r = BinF r r | UnF a r | LeafF a

treeFold :: (TreeF a r -> r) -> Tree a -> r
treeFold f (Leaf x)       = f (LeafF x)
treeFold f (Un x r)       = f (UnF x (treeFold f r))
treeFold f (Bin r1 r2)    = f (BinF (treeFold f r1) (treeFold f r2))

treeUnfold :: (r -> TreeF a r) -> r -> Tree a
treeUnfold f r = case f r of
LeafF x         -> Leaf x
UnF x r         -> Un x (treeUnfold f r)
BinF r1 r2      -> Bin (treeUnfold f r1) (treeUnfold f r2)


Of course, we can create deforestTree just as mechanically as before.

(Usually, we'd express treeFold more conveniently as:

treeFold' :: (r -> r -> r) -> (a -> r -> r) -> (a -> r) -> Tree a -> r


)

I'll leave out the details, I hope the pattern is obvious.