So I suggest all four folds. They are all useful and can all be implemented efficiently.
For certain classes of operation ⓧ, a tree-fold
(( _ ⓧ _) ⓧ (_ ⓧ _))
gives better complexity. Is there room for that, or is it too difficult to decide what to do about the unbalanced parts?
That would be covered by the Foldable instance since Foldable provides
fold :: (Data.Monoid.Monoid m) => t m -> m
which is exactly what you want. So we'd just want to provide a native implementation of it (rather than getting the default defined in terms of foldr).
Milan: so that's another good argument in favour of providing a Foldable instance. (And also of having foldl' and foldr' as Foldable class methods)
We actually do provide Foldable instance now, but we define only foldMap. I will add implementation for all other methods to achieve best complexity. Having foldl' and foldr' in Foldable class would be great. If that happens, we would definitely add specialised implementations. Cheers, Milan