<div dir="ltr">Upon consideration from a package management perspective this is probably easiest done by building a new small package to provide the functionality you want. That way we don&#39;t haphazardly change the transitive dependencies of a big chunk of the ecosystem and it can rest atop the various containers libraries. This also gives you a lot of opportunity to iterate on the API in public without incurring the instant rigidity of the Haskell Platform.</div>
<div class="gmail_extra"><br><br><div class="gmail_quote">On Sun, Sep 29, 2013 at 11:06 PM, Ryan Newton <span dir="ltr">&lt;<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Thanks Edward.  Good point about Brent&#39;s &#39;split&#39; package.  That would be a really nice place to put the class.  But it doesn&#39;t currently depend on containers or vector so I suppose the other instances would need to go somewhere else.  (Assuming containers only exported monomorphic versions.)<div>


<br></div><div>Maybe a next step would be proposing some monomorphic variants for the containers package.</div><div><br></div><div>I think the complicated bit will be describing how &quot;best-efforty&quot; splitting variants are:</div>


<div><ul><li>Is it guaranteed O(1) time and allocation?</li><li>Is the provided Int an upper bound?  Lower(ish) bound?  Or just a hint?</li></ul><div>With some data structures, there will be a trade-off between partition imbalance and the work required to achieve balance.  But with some data structures it is happily not a problem (e.g. Vector)!</div>


<div><br></div><div>But whether there&#39;s one variant or a few, I&#39;d be happy either way, as long as I get at least the cheap one (i.e. prefer imbalance to restructuring).  </div></div><span class="HOEnZb"><font color="#888888"><div>
<br></div><div>  -Ryan</div></font></span><div><div class="h5">

<div><br></div><div><br></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sun, Sep 29, 2013 at 8:20 AM, Edward Kmett <span dir="ltr">&lt;<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>&gt;</span> wrote:<br>


<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">I don&#39;t know that it belongs in the &quot;standard&quot; libraries, but there could definitely be a package for something similar.<div>


<div><div><br></div><div>ConstraintKinds are a pretty hefty extension to throw at it, and the signature written there prevents it from being used on ByteString, Text, etc.</div>
</div><div><br></div><div>This can be implemented with much lighter weight types though!</div><div><pre style="font-family:Consolas,&#39;Liberation Mono&#39;,Courier,monospace;font-size:12px;margin-top:0px;margin-bottom:0px;color:rgb(51,51,51);line-height:18px">

<div style="padding-left:10px"><span style="font-weight:bold"><br></span></div><div style="padding-left:10px"><span style="font-weight:bold">class</span> <span style="color:rgb(68,85,136);font-weight:bold">Partitionable</span> <span>t</span> <span style="font-weight:bold">where</span></div>



<div style="padding-left:10px">    <span>partition</span> <span style="font-weight:bold">::</span> <span style="color:rgb(68,85,136);font-weight:bold">Int</span> <span style="font-weight:bold">-&gt;</span> <span>t</span> <span style="font-weight:bold">-&gt;</span> <span>[</span><span>t</span><span>]</span><br>



</div></pre></div><div><br></div><div>Now ByteString, Text etc. can be instances and no real flexibility is lost, as with the class associated constraint on the argument, you&#39;d already given up polymorphic recursion.</div>



<div><br></div><div>There still remain issues. <font face="courier new, monospace">partition</font> is already established as the <font face="courier new, monospace">filter</font> that returns both the matching and unmatching elements, so the name is wrong.</div>



<div><br></div><div>This is a generalization of <font face="courier new, monospace">Data.List.splitEvery</font><font face="arial, helvetica, sans-serif">, perhaps it is worth seeing how many others can be generalized similarly and talk to Brent about adding, say, a </font><font face="courier new, monospace">Data.Split</font><font face="arial, helvetica, sans-serif"> module to his split package in the platform?</font></div>


<span><font color="#888888">
<div><br></div><div>-Edward</div><div><br></div><div><br></div><div><br></div></font></span></div></div><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sun, Sep 29, 2013 at 4:21 AM, Ryan Newton <span dir="ltr">&lt;<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>&gt;</span> wrote:<br>



<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>&lt;subject change&gt;</div><div><br></div><div>On Sun, Sep 29, 2013 at 3:31 AM, Mike Izbicki <span dir="ltr">&lt;<a href="mailto:mike@izbicki.me" target="_blank">mike@izbicki.me</a>&gt;</span> wrote:<br>





<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">I&#39;ve got a Partitionable class that I&#39;ve been using for this purpose:<div>





<a href="https://github.com/mikeizbicki/ConstraintKinds/blob/master/src/Control/ConstraintKinds/Partitionable.hs" target="_blank">https://github.com/mikeizbicki/ConstraintKinds/blob/master/src/Control/ConstraintKinds/Partitionable.hs</a></div>





</div></blockquote></div><div><br></div><div>Mike -- Neat, that&#39;s a cool library!</div><div><br></div><div>Edward --  ideally, where in the standard libraries should the Partitionable comonoid go?  </div><div><br></div>





<div>Btw, I&#39;m not sure what the ideal return type for comappend is, given that it needs to be able to &quot;bottom out&quot;.  Mike, our partition function&#39;s list return type seems more reasonable.  Or maybe something simple would be this:</div>





<div><div><br></div><div><font face="courier new, monospace"><b>class Partitionable t where</b></font></div><div><font face="courier new, monospace"><b>  partition :: t -&gt; Maybe (t,t)</b></font></div><div><br></div></div>





<div>That is, at some point its not worth splitting and returns Nothing, and you&#39;d better be able to deal with the &#39;t&#39; directly.</div><div><br></div><div>So what I really want is for the <b><font face="courier new, monospace">containers</font> package to please get some kind of Partitionable instances! </b> Johan &amp; others, I would be happy to provide a patch if the class can be agreed on. This is important because currently the balanced tree structure of Data.Set/Map is an <b>amazing and beneficial property</b> that is <i>not</i> exposed at all through the API.  </div>





<div>   For example, it would be great to have a parallel <font face="courier new, monospace">traverse_</font> for Maps and Sets in the <font face="courier new, monospace">Par</font> monad.  The particular impetus is that our new and enhanced Par monad makes extensive use of Maps and Sets, both the pure, balanced ones, and lockfree/inplace ones based on concurrent skip lists:</div>





<div><br></div><div>    <a href="http://www.cs.indiana.edu/~rrnewton/haddock/lvish/" target="_blank">http://www.cs.indiana.edu/~rrnewton/haddock/lvish/</a><br></div><div><br></div><div>Alternatively, it would be ok if there were a &quot;Data.Map.Internal&quot; module that exposed the Bin/Tip, but I assume people would rather have a clean Partitionable instance...<br>





</div>
<div><br></div><div>Best,</div><div>  -Ryan</div><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra"><div class="gmail_quote">On Sun, Sep 29, 2013 at 3:31 AM, Mike Izbicki <span dir="ltr">&lt;<a href="mailto:mike@izbicki.me" target="_blank">mike@izbicki.me</a>&gt;</span> wrote:<br>






<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">I&#39;ve got a Partitionable class that I&#39;ve been using for this purpose:<br>





<div><br><a href="https://github.com/mikeizbicki/ConstraintKinds/blob/master/src/Control/ConstraintKinds/Partitionable.hs" target="_blank">https://github.com/mikeizbicki/ConstraintKinds/blob/master/src/Control/ConstraintKinds/Partitionable.hs</a><br>







<br></div><div>The function called &quot;parallel&quot; in the HLearn library will automatically parallelize any homomorphism from a Partionable to a Monoid.  I specifically use that to parallelize machine learning algorithms.<br>







</div><div class="gmail_extra"><br></div><div class="gmail_extra">I have two thoughts for better abstractions:<br><br>1)  This Partitionable class is essentially a comonoid.  By reversing the arrows of mappend, we get:<br>







<br></div><div class="gmail_extra">comappend :: a -&gt; (a,a)<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">By itself, this works well if the number of processors you have is a power of two, but it needs some more fanciness to get things balanced properly for other numbers of processors.  I bet there&#39;s another algebraic structure that would capture these other cases, but I&#39;m not sure what it is.<br>







</div><div class="gmail_extra"><br></div><div class="gmail_extra">2) I&#39;m working with parallelizing tree structures right now (kd-trees, cover trees, oct-trees, etc.).  The real problem is not splitting the number of data points equally (this is easy), but splitting the amount of work equally.  Some points take longer to process than others, and this cannot be determined in advance.  Therefore, an equal split of the data points can result in one processor getting 25% of the work load, and the second processor getting 75%.  Some sort of lazy Partitionable class that was aware of processor loads and didn&#39;t split data points until they were needed would be ideal for this scenario.<br>







</div><div class="gmail_extra"><br><div class="gmail_quote"><div><div>On Sat, Sep 28, 2013 at 6:46 PM, adam vogt <span dir="ltr">&lt;<a href="mailto:vogt.adam@gmail.com" target="_blank">vogt.adam@gmail.com</a>&gt;</span> wrote:<br>







</div></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div><div><div>On Sat, Sep 28, 2013 at 1:09 PM, Ryan Newton &lt;<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>&gt; wrote:<br>








&gt; Hi all,<br>
&gt;<br>
&gt; We all know and love Data.Foldable and are familiar with left folds and<br>
&gt; right folds.  But what you want in a parallel program is a balanced fold<br>
&gt; over a tree.  Fortunately, many of our datatypes (Sets, Maps) actually ARE<br>
&gt; balanced trees.  Hmm, but how do we expose that?<br>
<br>
</div>Hi Ryan,<br>
<br>
At least for Data.Map, the Foldable instance seems to have a<br>
reasonably balanced fold called fold (or foldMap):<br>
<br>
&gt;  fold t = go t<br>
&gt;    where   go (Bin _ _ v l r) = go l `mappend` (v `mappend` go r)<br>
<br>
This doesn&#39;t seem to be guaranteed though. For example ghc&#39;s derived<br>
instance writes the foldr only, so fold would be right-associated for<br>
a:<br>
<br>
&gt; data T a = B (T a) (T a) | L a deriving (Foldable)<br>
<br>
Regards,<br>
Adam<br></div></div>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br></div></div>
</blockquote></div><br></div></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div></div></div></div>
</blockquote></div><br></div>