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

[Neil Mitchell]

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.

Thanks

Neil