Proposal #3271: new methods for Data.Sequence
ross at soi.city.ac.uk
Thu Aug 6 07:26:15 EDT 2009
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))
More information about the Libraries