[Haskell-cafe] Re: (flawed?) benchmark : sort
Adrian Hey
ahey at iee.org
Fri Mar 14 09:16:10 EDT 2008
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
More information about the Haskell-Cafe
mailing list