Re: Various folds in the containers package

On Thu, Jun 16, 2011 at 6:23 AM, Johan Tibell wrote:

On Thu, Jun 16, 2011 at 11:39 AM, 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?

I've been thinking about adding monoidal fold to unordered-containers. One interesting property is that you can evaluate branches in parallel. Perhaps containers should have one too.

Yes please. Note that monoidal fold + fmap is cata on leaf-labeled trees. -Jan