General, state-passing fold over a tree [Was: Threading a state through a fold?]
ol...@pobox.com
a tree. To be more precise, the problem is to traverse a tree and to
build a new one of the same structure. The mapping between the
corresponding nodes in the old and the new trees is a function of old
node's value and of the history of the traversal. Pattern-matching and
recursion make the problem straightforward. However, there is a catch:
Can we solve the problem in a combinatorial way? That is, can we
separate the task of traversal and recursion from the task of
transformation of a node and a state? The first task is preferably to
be done by fold.
In particular, Neel Krishnaswami posed a problem of renumbering a
tree: "replacing" the value in a Node with a number: the Node's order
in a traversal of the tree.
Neel Krishnaswami and Daniel C. Wang determined that you need either a
continuation-based fold or a higher-order fold. It's exactly the same
result mentioned in a paper
"The Under-Appreciated Unfold" by Geremy Gibbons and Geraint Jones
ICFP'98
The topic of that paper is expressing a breadth-first traversal over a
tree as a tree fold. The paper defines the fold over trees. As the
authors showed, unfold is far more suitable for their task. [Daniel
C. Wang also gave a state monad approach to the renumber problem].
This article discusses a more general fold over trees -- the one that
makes passing of a state easy.
Here's our (recursive) datatype
data Tree a = Nd a [Tree a] deriving Show
type Forest a = [Tree a]
It's a more general data structure than discussed by Neel
Krishnaswami: it's more than a binary tree.
Our generalized fold -- a traversal combinator -- is given by the
following equations
foldt fdown fup fhere (Nd val kids) seed =
fup val seed (foldf fdown fup fhere kids (fdown val seed))
foldf fdown fup fhere kids seed =
foldr (\kid seed -> foldt fdown fup fhere kid (fhere seed)) seed kids
The renumber function can easily be expressed as
renumber count tree =
let fup _ (_,forest_here) (count_below,forest_below) =
(count_below + 1, (Nd count_below forest_below):forest_here)
fdown _ (count,forest) = (count,[])
in foldt fdown fup id tree (0,[])
Indeed, the mapping and the state maintenance is completely separated
from the traversal. The former task (functions fup and fdown) is
_non_-recursive.
Example:
tree = Nd 'a' [Nd 'b' [Nd 'c' [], Nd 'd' []], Nd 'e' []]
renumber 0 tree
===> (5,[Nd 4 [Nd 3 [Nd 2 [],Nd 1 []],Nd 0 []]])
tree1 = Nd 'x' [Nd 'z' [], tree]
renumber 0 tree1
===> (7,[Nd 6 [Nd 5 [],Nd 4 [Nd 3 [Nd 2 [],Nd 1 []],Nd 0 []]]])
tree2 = Nd 'x' [Nd 'z' [], tree, Nd 'w' [Nd 's' [], Nd 't' [], Nd 'u' []]]
renumber 0 tree2
===> (11,[Nd 10 [Nd 9 [],Nd 8 [Nd 7 [Nd 6 [],Nd 5 []],Nd 4 []],
Nd 3 [Nd 2 [],Nd 1 [],Nd 0 []]]])
The generalized fold, foldt, has been used in practice for a far more
complex application -- a purely-functional XML parser (toolkit),
supporting XML namespaces, parsed entities, xml:space, CDATA sections
and validations. Indeed, XML parsing is a tree mapping: from a tree
laid out as an XML document, to a DOM or other XML Infoset tree. See
the detailed title comments in
http://pobox.com/~oleg/ftp/Scheme/SSAX.scm