Various folds in the containers package
fox at ucw.cz
Mon Jun 20 18:49:05 CEST 2011
> > > 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
We actually do provide Foldable instance now, but we define only
foldMap. I will add implementation for all other methods to achieve best
Having foldl' and foldr' in Foldable class would be great. If that
happens, we would definitely add specialised implementations.
More information about the Libraries