<div>Would there be anything wrong with a Data.Set simply chopping off half its (balanced) tree and returning two approximately balanced partitions -- i.e. Data.Set.split without the pivot argument? Even though it can't quite be constant-time (still need rebalancing) it could still be cheaper than Data.Set.split, right? In the context of Set.hs, I'm thinking along the lines of something like the following:</div>
<div><br></div><div><div><font class="Apple-style-span" face="'courier new', monospace">cleave :: Set a -> (Set a, Set a)</font></div><div><font class="Apple-style-span" face="'courier new', monospace">cleave Tip = (Tip, Tip)</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace">cleave (Bin _ x l r)</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> | size l > size r = (l, insertMin x r)</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> | otherwise = (insertMax x l, r)</font></div></div><div><br></div><div>For one thing, this seems like the proposed function would be useful for consuming a set in parallel, similar to Guy Steele's arguments in recent talks (see <span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; "><a href="http://research.sun.com/projects/plrg/Publications/ICFPAugust2009Steele.pdf" target="_blank" style="color: rgb(17, 65, 112); ">Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful</a></span>). That is, one splits a tree and uses "par" to process the left and right half in parallel, enabling </div>
<div><br></div><div>Alternatively, it would be simple to provide a parallel version of mapMonotonic that does this internally, i.e.: </div><div><br></div><div><div><font class="Apple-style-span" face="'courier new', monospace">mapMonotonic _ Tip = Tip</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace">mapMonotonic f (Bin sz x l r) =</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> Bin sz (f x) (mapMonotonic f l) (mapMonotonic f r)</font></div>
</div><div><br></div><div>Becomes something like:</div><div><br></div><div><div><font class="Apple-style-span" face="'courier new', monospace">parMapMonotonic f (Bin sz x l r) =</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> par left $ seq right $ </font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> Bin sz (f x) left right</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> where </font></div><div><font class="Apple-style-span" face="'courier new', monospace"> left = mapMonotonic f l </font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> right = mapMonotonic f r</font></div></div><div><br></div><div>Cheers,</div><div> -Ryan</div><div><br></div>