[Haskell-cafe] What class for splittable data / balanced-fold?

[Jan-Willem Maessen]

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
properly anyway.

-Jan-Willem Maessen
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130929/37149cd3/attachment.htm>