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

[Bertram Felgenhauer]

Duncan Coutts wrote:
> So can anyone break this hypothesis?
> 
>   nub . sort = map head . group . sort

Just make Eq and Ord instances that are completely unrelated, say

    data Foo = Foo Int Int deriving Show

    instance Eq Foo where
        Foo a _ == Foo b _ = a == b

    instance Ord Foo where
        Foo _ a `compare` Foo _ b = a `compare` b

    example = [Foo 0 1, Foo 0 2, Foo 1 1]

With these instances

    nub . sort

does something well-defined; sort only uses `compare` and nub only uses
(==). Note that Data.List.sort actually provides a stable sort. I don't
know if that's specified anywhere, but it's true for both Data.List and
for the Haskell report implementation of sort.

The rule

>   nub . sort = map head . group . sort

on the other hand relies on a correspondence between Eq and Ord and
breaks:

    > nub . sort $ example
    [Foo 0 1,Foo 1 1]
    > map head . group . sort $ example
    [Foo 0 1,Foo 1 1,Foo 0 2]

More precisely the rule works iff  a <= b && b <= c && a == c
implies  a == b.

I'm not sure whether mismatching Eq and Ord [*] instances should be a
programmer error, but if so this needs to be stated somewhere. Right
now, Data.List has no such restriction.

Bertram

[*] Ideally, the correspondance should be that
  (a == b) == (a <= b && b <= a)