[Haskell-cafe] What class for splittable data / balanced-fold?
jmaessen at alum.mit.edu
Sun Sep 29 15:37:54 CEST 2013
On Sat, Sep 28, 2013 at 1:09 PM, Ryan Newton <rrnewton at gmail.com> wrote:
> 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 library<http://hackage.haskell.org/package/monad-par-extras-0.3.3/docs/Control-Monad-Par-AList.html>
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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe