Proposal #3271: new methods for Data.Sequence

[Louis Wasserman]

The faster sort for Data.Sequence is a heapsort based on a pairing heap
implementation.  The only way I can think of to make it stable is to index
the entire sequence and then add indices to the comparisons, which removes
almost all of the benefit of the heapsort implementation:

Times (ms)
                 min      mean    +/-sd    median    max
to/from list:  106.742  111.269    4.831  110.207  138.638
pairing heap:   62.896   66.066    2.410   65.433   74.471
stable pheap:   95.600  102.381    5.807  100.744  120.395

Even worse, the stable heapsort becomes genuinely worse when there's memory
to spare; with +RTS -H128m:

Times (ms)
                 min      mean    +/-sd    median    max
to/from list:   53.675   84.407   14.130   86.319  108.553
pairing heap:   62.492   77.065    9.649   78.883  104.606
stable pheap:   70.437   97.718   15.332  100.548  134.624

Perhaps the most reasonable compromise would be to include the faster sort
method, but name it sortBy' or something else indicating that it is
nonstandard.  (That still leaves open the question of whether the stable
sort method should be the Data.List conversion, or the stable heapsort.)

I had forgotten to mention that zipWith had been modified to a one-liner
with mapAccumL, which actually proved faster than my implementation.

Louis Wasserman
wasserman.louis at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20090717/dcad529c/attachment.html