[Haskell-cafe] Re: (flawed?) benchmark : sort

[Adrian Hey]

Neil Mitchell wrote:
> Hi
> 
>>  > instance Ord Foo where
>>  >     compare (Foo a _) (Foo b _) = compare a b
>>
>>  I would consider such an Ord instance to be hopelessly broken, and I
>>  don't think it's the responsibility of authors of functions with Ord
>>  constraints in their sigs (such as sort) to consider such possibilities
>>  or specify and control the behaviour of their behaviour for such
>>  instances. Trying to do this is what leads to horrors such as the "left
>>  biasing" of Data.Map (for example).
> 
> The sort in Haskell is specified to be "stable". What that means is
> that the above ord relation is fine. The above ordering observes all
> the necessary mathematical definitions of ordering, assuming an Eq of:
> 
> instance Eq Foo where
>     (==) (Foo a _) (Foo b _) = (==) a b
> 
>>  Unfortunately the Haskell standards don't currently specify sane laws
>>  for Eq and Ord class instances, but they should. Otherwise knowing a
>>  type is an instance of Ord tells me nothing that I can rely on.
> 
> Please give the sane law that this ordering violates. I can't see any!

The Eq instance you've given violates the law that (x == y) = True
implies x = y. Of course the Haskell standard doesn't specify this law,
but it should.

The Haskell standard doen't even specify that compare x y = EQ implies
(x == y) = True, but again it should (what's the purpose of the Eq
constraint on Ord class otherwise).

> What if I had made the definition of Foo:
> 
> data Foo = Foo Int (Int -> Int)
> 
> Now, is the only possible answer that any Ord instance for Foo is wrong?

Yes, if the Foo constuctor is exported. If it's scope confined to one
module then you could maintain the invariant that the same function is
always associated with a given Int. However, if this is the case then
the issue you raise wrt sort behaviour is irrelevant.

Regards
--
Adrian Hey