Various folds in the containers package

[Duncan Coutts]

On Thu, 2011-06-16 at 10:39 +0100, Jon Fairbairn wrote:
> Duncan Coutts <duncan.coutts at googlemail.com> writes:
> 
> > 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)

Duncan