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

[Adrian Hey]

Dan Weston wrote:
> 6.3.2 (The Ord Class):
> 
> "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)

Thanks Dan. I didn't grasp the significance of this at first, but
I believe you are correct. But maybe it should be "=" not "=="
in the last line?

>   forall f . (compare x y == EQ and (f x or f y is defined))
>                  ==> f x = f y)

So assuming your (and my) logic is correct, the existing report text
does indeed settle the original dispute that sparked this thread.
Essentially you can't have 2 distinct values that compare equal,
so if they do then they must be indistinguishable? Is that right?

So there is no need for the sort on a list of elements whose type
is an instance of Ord to be "stable" as the difference between
the results of a stable and unstable sort cannot be observable
for any (correct) Ord instance (assuming the the instances compare
method was used to perform the sort).

So if we have a compare method on this type we can establish the
== method:
  x == y = case compare x y of
           EQ -> True
           _  -> False

and from this it follows that (x == y) = True implies x and y are
indistingushable.

So I believe for types that are instances of both Eq and Ord, this
settles the question of what (x == y) = True implies.

So now I'm wondering what about types that are instances of Eq
but not of Ord? Well from para. 6.3.1

"The Eq class provides equality (==) and inequality (/=) methods."

Well I guess assuming that saying two values are "equal" is another
way of saying they are indistinguishable then I think it's pretty
clear what the report is saying. This interpretation also ensures
consistency between Eq/Ord instances and Eq only instances.

Assuming this is all correct, I think I can sleep easier now I can
forget about all this "things being equal and not equal at the same
time" craziness, at least for Eq/Ord instances that are compliant
with the standard (which are the only ones I care about).

I think anyone wanting standard classes with different mathematical
properties should define them, stick them in Hackage and propose
them for Haskell-prime (if that's still happening?)

Regards
--
Adrian Hey