Proposal #3271: new methods for Data.Sequence

[Louis Wasserman]

Done.  See the new patch
here<http://hackage.haskell.org/trac/ghc/attachment/ticket/3271/new-methods-for-data_sequence.4.dpatch>
.

Key notes:

Among other things, I manually deforested the stable sorting algorithm,
resulting in a moderate performance gain on simply using Data.List.sortBy.
The current benchmarks indicate:

   - unstableSort is typically 40% faster than sort, with no RTS options.
   - With memory to spare, unstableSort is typically 15% faster than sort.
   - On sorted data with no RTS options, unstableSort is nearly 70% faster
   than sort.
   - On sorted data with memory to spare, unstableSort is nearly 60% faster
   than sort.

(Did I mention I think pairing heaps are excellent?)

Among all the methods I added to Data.Sequence, the most code-intensive are
tails/inits and consDigitToTree/snocDigitToTree.

The second was more intensively used with some previous zipWith
implementations that have since been replaced, but they add moderate speed
improvements to the significant amount of already-bulky code for appending
two sequences, and I can live with that on my conscience.

The code for tails/inits provides actual, concrete algorithmic benefits, in
particular that evaluating a tail from the sequence of tails is O(log n), as
opposed to O(n), but the entire tail sequence still only takes O(n) to
build.  In particular, evaluating one tail and then the tail just after it
is still every bit as cheap as it should be.  Finally, evaluating the whole
sequence of tails with this method is even faster than scanr (<|) empty, or
even a similar scanl, which is pretty nice.

Louis Wasserman
wasserman.louis at gmail.com


On Sun, Jul 19, 2009 at 9:57 PM, Evan Laforge <qdunkan at gmail.com> wrote:

> > Again, I'd like to propose a compromise: make Data.Sequence.sortBy cmp be
> > either fromList2 . Data.List.sortBy cmp . toList, or use the stable
> > pairing-heap sort, and add a second sorting method, sortBy', that is
> > unstable but faster.
>
> Sounds good to me but how about calling them unstableSortBy and
> unstableSort?
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20090720/acc013de/attachment.html