Done. See the new patch here.

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@gmail.com

On Sun, Jul 19, 2009 at 9:57 PM, Evan Laforge <qdunkan@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?