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

[Lennart Augustsson]

I have certainly used Eq and Ord similar to the ones in my example.
I know under what circumstances I can call what library functions,
but the compiler doesn't.  It should not make any unprovable assumptions
about my code; I'd be very perturbed if it did.

	-- Lennart

On Mar 19, 2007, at 23:05 , Duncan Coutts wrote:

> 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