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