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

[Duncan Coutts]

On Mon, 2007-03-19 at 19:43 +0000, Lennart Augustsson wrote:
> As I pointed out in the GHC trac report, this rule is wrong.  E.g.,
> 
> data T = T Int Int deriving (Ord, Show)
> instance Eq T where
>      T x _ == T y _ =  x == y
> 
> ts = [T 1 1, T 1 undefined]

So the problem in that example is that if we nub first then we get
[T 1 1] and sorting that is presumably fine, however if we sort we
compare both fields.

My grumble here is that your Eq and Ord instances are not in agreement
with each other. If you can claim that they're equal by only comparing
the first components then surely you must for Ord too.

Isn't some law being violated here:
	T 1 0 < T 1 1
and yet	T 1 0 == T 1 1

but shouldn't a < b imply that a != b

H98 requires that Eq and Ord be equality classes and total orders, does
it say nothing about any relationship between the two, that they be in
any way consistent?

So one could say that we can't really rely on any laws that should go
along with type class instances, but that's clearly not right since then
we cannot sort!

If we cannot rely on Ord then the current Data.List.sort implementation
is wrong because it gives different answers from the H98 spec sort when
the Ord instance is not a total order (this is easiest to see with
sortBy).

Duncan