Various folds in the containers package
jmaessen at alum.mit.edu
Fri Jun 17 20:24:22 CEST 2011
On Thu, Jun 16, 2011 at 6:23 AM, Johan Tibell <johan.tibell at gmail.com> wrote:
> On Thu, Jun 16, 2011 at 11:39 AM, Jon Fairbairn
> <jon.fairbairn at cl.cam.ac.uk> 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?
> 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.
More information about the Libraries