[trac@galois.com: Re: [GHC] #1218: Add sortNub and sortNubBy to Data.List]

Neil Mitchell ndmitchell at gmail.com
Sun Mar 18 22:02:18 EDT 2007

Hi Donald,

> I propose we *do not* change the api to add the special case:
>     sortNub = sort . nub
>             = map head . group . sort
> and instead add a rewrite rule to Data.List to provide this
> optimisation.
>  {-# RULES
>  "sort/nub" sort . nub = map head . group . sort
>    #-}

Yes, but this is only available for GHC, not for Haskell...

A lot of the changes that have been made recently (i.e. the ByteString
stuff) have been performance optimisations for GHC, but not for other
Haskell compilers. Talking to Malcolm recently he said that String
outperforms ByteString with nhc.

I think its important when you are using an algorithm to say "I want
to use an O(n log n) algorithm instead of an O(n^2) one" and have the
compiler obey you unconditionally. If the compiler wants to replace
the O(n^2) one as well, that is just groovy, but your big-O shouldn't
depend on compiler specific rules.



More information about the Libraries mailing list