haskell-cafe@haskell.org
[Top] [All Lists]

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

Subject: Re: [Haskell-cafe] Re: (flawed?) benchmark : sort
From: Adrian Hey
Date: Fri, 14 Mar 2008 13:16:10 +0000
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

































_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@xxxxxxxxxxx
http://www.haskell.org/mailman/listinfo/haskell-cafe

<Prev in Thread] Current Thread [Next in Thread>