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

Bertram Felgenhauer bertram.felgenhauer at googlemail.com
Wed Mar 21 06:48:13 EDT 2007

```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)
```