Re: Various folds in the containers package

On Thu, 2011-06-16 at 10:39 +0100, Jon Fairbairn wrote:

Duncan Coutts 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