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

[Duncan Coutts]

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