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.
See also: