[Haskell-cafe] Why isn't there a cheaper "split-in-two" operation for Data.Set?

[Ryan Newton]

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 at 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20101019/5c1fd7b2/attachment.html