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." 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 |

Previous by Date: | [Haskell-cafe] HFuse: ls fails in HelloFS, Georg Neis |
---|---|

Next by Date: | Re[2]: [Haskell-cafe] Problem making a program in ghc, Bulat Ziganshin |

Previous by Thread: | Re: [Haskell-cafe] Re: (flawed?) benchmark : sort, ajb |

Next by Thread: | [Haskell-cafe] Re: (flawed?) benchmark : sort, Aaron Denney |

Indexes: | [Date]
[Thread]
[Top]
[All Lists] |