<div dir="ltr"><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Sep 28, 2013 at 1:09 PM, Ryan Newton <span dir="ltr"><<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi all,<div><br></div><div>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?</div>
<div><br></div><div>It seems like it would be nice to have a<b> standard class t</b>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 <a href="http://hackage.haskell.org/package/monad-par-extras-0.3.3/docs/Control-Monad-Par-AList.html" target="_blank">append-lists within the monad-par library</a>.</div>
</div></blockquote><div><br></div><div style>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.</div>
<div style><br></div><div style>So I'd just go with a hand-written Foldable instance here.</div><div><br></div><div style>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.</div>
<div style><br></div><div style>-Jan-Willem Maessen</div></div></div></div>