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