More on Tree Folds

After some thought, I think I have the definitions for left and right fold on a tree:

foldrTree :: (a -> b -> b) -> b -> InternalTree a -> b
foldrTree f z ILeaf = z
foldrTree f z (IBranch a x y) = foldrTree f (f a (foldrTree f z y)) x

foldlTree :: (a -> b -> a) -> a -> InternalTree b -> a
foldlTree f z ILeaf = z
foldlTree f z (IBranch a x y) = foldlTree f (f (foldlTree f z x) a) y

Of course, these folds are simplified: they don’t have a separate function for dealing with leaves and branches. This leads to things like flatten only working one way, i.e.
foldrTree (:) [] t
works because (:) will accumulate values onto a list properly from the right, but
foldlTree (:) [] t
gives a type error (because (:) cannot append a value onto a list working from the left).

One Response to “More on Tree Folds”

  1. Per Vognsen Says:

    The natural definition of folding would have this type signature:

    foldrT :: (a -> b -> b -> b) -> b -> Tree a -> b

    There’s a general cookbook method for deriving the fold for any so-called “polynomial data type” that generates both the above foldrT and the usual foldr for lists.

Leave a Reply