The old Google Groups will be going away soon, but your browser is incompatible with the new version.
General, state-passing fold over a tree [Was: Threading a state through a fold?]
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 1 message

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Jun 22 2001, 8:58 pm
Newsgroups: comp.lang.functional
From: o...@pobox.com (o...@pobox.com)
Date: 22 Jun 2001 17:58:19 -0700
Local: Fri, Jun 22 2001 8:58 pm
Subject: General, state-passing fold over a tree [Was: Threading a state through a fold?]
Neel Krishnaswami posed a problem of mapping a stateful function over
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
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