That sounds good to me.  In any case the parallel map/fold operations by themselves shouldn't compromise the abstraction.

Perhaps an eventual solution would be to start including parallel maps/folds right inside the standard libraries.  I haven't began testing this yet but it would seem that all the balanced tree implementations are good candidates for a little `par` treatment.  Has this been tried somewhere already? 
   Alas, having par/nonpar versions of library functions compounds the already present monadic/non-monadic schism...

Anyway, right this second I'm primarily interested in speeding up difference and intersection -- that would be really useful for a simple utility I've been using that compares files as Maps of word-tuples and runs rather slowly (http://hackage.haskell.org/package/wordsetdiff).

Cheers,
-Ryan


On Mon, Oct 4, 2010 at 11:00 AM, Bertram Felgenhauer <bertram.felgenhauer@googlemail.com> wrote:
Ryan Newton wrote:
> Would there be anything wrong with a Data.Set simply chopping off half its
> (balanced) tree and returning two approximately balanced partitions
...
> cleave :: Set a -> (Set a, Set a)
> cleave Tip = (Tip, Tip)
> cleave (Bin _ x l r)
>   | size l > size r = (l, insertMin x r)
>   | otherwise       = (insertMax x l, r)

This function would expose some of the internal structure of Set - i.e.
there could be equal sets  s1 == s2  with  cleave s1 /= cleave s2.

Maybe a better idea than to expose such a function would be to split
Data.Set into Data.Set.Internal and Data.Set, where Data.Set.Internal
would export the actual Tip and Bin constructors. Then people who want
to break the abstraction, for example to experiment with parallel folds,
could do that easily.

regards,

Bertram