I'm afraid you have only three choices:
- use a second-order fold
- use an enhanced fold-like operator such as foldts
- give up on higher-order combinators and use recursion
directly
The second-order fold is very inefficient -- it has large latency and
it creates as many closures as there are nodes in the tree. The
second-order fold basically replaces the tree of nodes with the tree
of closures. After the latter is constructed, it is applied to the
accumulator.
folts is defined as follows:
data Tree = Leaf String | Nd [Tree]
foldts fdown fup fhere seed (Leaf str) = fhere seed str
foldts fdown fup fhere seed (Nd kids) =
fup seed $ foldl (foldts fdown fup fhere) (fdown seed) kids
Example: computing an MD5 digest of a tree
md5Init:: MD5Context
md5Update:: String -> MD5Context -> MD5Context
md5Final:: MD5Context -> String
tree_digest2 = md5Final . (foldts fd fu fh md5Init)
where fh ctx str = md5Update "/leaf" $ md5Update str $ md5Update "leaf" ctx
fd ctx = md5Update "node" ctx
fu _ ctx = md5Update "/node" ctx
Finally, the breadth-first tree traversal:
breadth_first = foldr (x seed -> foldl (flip (:)) seed x) [] . foldts fdown fup fhere [[]]
where
fhere (level_here:levels_below) str = (str:level_here):levels_below
fdown (_:[]) = []:[]
fdown (_:levels_below) = levels_below
fup (level_here:levels_below) new_levels_below = level_here:new_levels_below
For example,
breadth_first (Nd [Leaf "0", Nd [Leaf "11", Leaf "12"], Leaf "2"])
evaluates to
["0","2","11","12"]
Note that
foldr (x seed -> foldl (flip (:)) seed x) []
is an efficient implementation of
concat . map reverse
You can't efficiently implement the breadth_first with the first-order
fold (and the second-order fold is inefficient). This was the subject
of Gibbons and Jones' paper.
| 
Folding over trees