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
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))
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 :: (a -> r -> r) -> r -> List a -> r
foldr f z = foldList g
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 :: (r -> Maybe (a, r)) -> r -> [a]
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))
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.