Proposal #3271: new methods for Data.Sequence

[Ross Paterson]

On Thu, Aug 06, 2009 at 08:22:28AM +0100, Simon Peyton-Jones wrote:
> On 03 August 2009 20:29, Ross Paterson wrote:
> | On Mon, Jul 20, 2009 at 02:33:52PM -0400, Louis Wasserman wrote:
> | > Among other things, I manually deforested the stable sorting algorithm,
> | > resulting in a moderate performance gain on simply using Data.List.sortBy.
> | 
> | That's not supposed to be necessary, because toList is supposed to fuse
> | with list consumers.  Unfortunately it doesn't in cases like this because
> | it doesn't get inlined, even if we add an INLINE pragma, due to GHC bug
> | #2353.  If the GHC bug isn't fixed, I think the next best thing would
> | be to force the inlining of toList with a RULES pragma in Data.Foldable.
>
> I will look into this during August.  Add yourself to the cc list for
> #2353 if interested.

OK, I'll add INLINE toList to Data.Foldable and wait till it starts working.
(If it doesn't, I can add RULES to unconditionally force the expansion.)

In any case we won't need to manually deforest Data.Sequence.sortBy.
The naive version will (soon) be just as fast:

sortBy :: (a -> a -> Ordering) -> Seq a -> Seq a
sortBy cmp xs = fromList2 (length xs) (Data.List.sortBy cmp (toList xs))