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