Proposal #3271: new methods for Data.Sequence

[Ross Paterson]

On Thu, Jul 16, 2009 at 07:48:33PM -0400, Louis Wasserman wrote:
>   * I completely rewrote the sorting method.  The sort is unstable,
>     but it is 40 lines (much more maintainable than the several-hundred
>     line implementation from earlier) and runs *twice as fast as*
>     (fromList . Data.List.sort . toList) for n=50000.  (For sorted
>     lists, it clocks in at about 4x faster.)

How does it compare against

sortBy cmp xs = fromList2 (size xs) (Data.List.sortBy cmp (toList xs))

I'm inclined to agree with John that stability is important in a general
purpose sort.

>   * partition is now in fact implemented via a simple foldl', which
>     is actually faster than my old, several-dozen-line implementation
>     as well as obviously simpler.
>
> I had forgotten to mention that zipWith had been modified to a one-liner
> with mapAccumL, which actually proved faster than my implementation.

That is good news indeed.