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

[Daniel Fischer]

Am Montag, 10. März 2008 20:12 schrieb Neil Mitchell:
> Hi
>
> >  "The Ord class is used for totally ordered datatypes."
> >
> >  This *requires* that it be absolutely impossible in valid code to
> >  distinguish equivalent (in the EQ sense, not the == sense) things via
> >  the functions of Ord. The intended interpretation of these functions is
> >  clear and can be taken as normative:
> >
> >    forall f . (compare x y == EQ and (f x or f y is defined))
> >                   ==> f x == f y)
>
> Are you sure? I would have read this as the ordering must be
> reflexive, antisymetric and transitive - the standard restrictions on
> any ordering. See http://en.wikipedia.org/wiki/Total_ordering
>

But antisymmetry means that (x <= y) && (y <= x) ==> x = y, where '=' means 
identity. Now what does (should) 'identity' mean?
Depends on the type, I dare say. For e.g. Int, it should mean 'identical bit 
pattern', shouldn't it? For IntSet it should mean 'x and y contain exactly 
the same elements', the internal tree-structure being irrelevant. But that 
means IntSet shouldn't export functions that allow to distinguish (other than 
by performance) between x and y.

In short, I would consider code where for some x, y and a function f we have
(x <= y) && (y <= x) [or, equivalently, compare x y == EQ] but f x /= f y
broken indeed. 

So for
data Foo = Foo Int (Int -> Int),
an Ord instance via compare (Foo a _) (Foo b _) = compare a b
is okay if Foo is an abstract datatype and outside the defining module it's 
guaranteed that 
compare (Foo a f) (Foo b g) == EQ implies (forall n. f n == g n), but not if 
the data-constructor Foo is exported.

> Thanks
>
> Neil