[email protected]
[Top] [All Lists]

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

 Subject: Re: [Haskell-cafe] Re: (flawed?) benchmark : sort Adrian Hey 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 [email protected]/* */ http://www.haskell.org/mailman/listinfo/haskell-cafe ```