Unfortunately the Haskell standards don't currently specify sane laws for Eq and Ord class instances, but they should.
In fact there are requirements in the Haskell98 report: 6.3 Standard Haskell Classes Note the word "reasonable" in the paragraph below: "Default class method declarations (Section 4.3) are provided for many of the methods in standard classes. A comment with each class declaration in Chapter 8 specifies the smallest collection of method definitions that, together with the default declarations, provide a reasonable definition for all the class methods." This (coupled with the premise that anything not required is optional) means that default definitions are not normative, so the following Ord default code comment need not hold: "-- Note that (min x y, max x y) = (x,y) or (y,x)" However, the report text is normative: 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) There is an (seriously insane but required by the total ordering, and in any case) officially encouraged use of left-bias in sum types: "The declared order of the constructors in the data declaration determines the ordering in derived Ord instances." Perhaps in Haskell' the total ordering requirement can be loosened to a partial order (say in a class between Eq and Ord), with comparePartial :: a -> a -> PartialOrdering? Dan Adrian Hey wrote:
Neil Mitchell wrote:
2) What does it do with duplicate elements in the list? I expect it deletes them. To avoid this, you'd need to use something like fromListWith, keeping track of how many duplicates there are, and expanding at the end.
That would be wrong. Consider:
data Foo = Foo Int Int
instance Ord Foo where compare (Foo a _) (Foo b _) = compare a b
I would consider such an Ord instance to be hopelessly broken, and I don't think it's the responsibility of authors of functions with Ord constraints in their sigs (such as sort) to consider such possibilities or specify and control the behaviour of their behaviour for such instances. Trying to do this is what leads to horrors such as the "left biasing" of Data.Map (for example).
Unfortunately the Haskell standards don't currently specify sane laws for Eq and Ord class instances, but they should. Otherwise knowing a type is an instance of Ord tells me nothing that I can rely on.
Regards -- Adrian Hey
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe