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

On Mon, 2007-03-19 at 11:02 +1100, Donald Bruce Stewart wrote:

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 #-}

Though of course we'd want to use the more efficient implementation than that. One can write a sort that directly eliminates duplicates, and I think you'd want a rule for nub . sort as well as sort . nub. And while we're at it we can add a rule to rewrite all the places people have used map head . group . sort (or the goupBy f . sortBy f equivalents) to this equals-eliminating sort implementation. Duncan