On Sat, Sep 28, 2013 at 1:09 PM, Ryan Newton
Hi all,
We all know and love Data.Foldable and are familiar with left folds and right folds. But what you want in a parallel program is a balanced fold over a tree. Fortunately, many of our datatypes (Sets, Maps) actually ARE balanced trees. Hmm, but how do we expose that?
It seems like it would be nice to have a* standard class t*hat allows you to split a datatype into roughly even halves, until you get down to the leaves. This goes along with Guy Steele's argument that we should use "append lists" as primitive rather than "cons-lists", and it's why we added append-lists within the monad-par libraryhttp://hackage.haskell.org/package/monad-par-extras-0.3.3/docs/Control-Monad... .
Interestingly, in my Fortress days we looked at both using a split-like interface and at a more foldMap / reduce - like interface, and it seemed like the latter worked better – it requires a lot less boilerplate for controlling recursion, and better matches the fanout of whatever structure you're actually using underneath. So I'd just go with a hand-written Foldable instance here. But I'd love to hear if you've come up with an application that requires split itself, and that *isn't* zip. I recall we decided zip was better done with element-and-index iteration over one of the structures and indexing into the other since most tree structures don't actually zip properly anyway. -Jan-Willem Maessen