I'm afraid you have only three choices:
 use a secondorder fold
 use an enhanced foldlike operator such as foldts
 give up on higherorder combinators and use recursion
directly
The secondorder fold is very inefficient  it has large latency and
it creates as many closures as there are nodes in the tree. The
secondorder 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 breadthfirst 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 firstorder
fold (and the secondorder fold is inefficient). This was the subject
of Gibbons and Jones' paper.
