## 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).

August 6th, 2007 at 2:32 am

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.