On the other hand, though the behavior of == is not defined by the
Report, it does require in 6.3.1 that if compare is defined, then ==
must be defined. That strongly implies a semantic causal link (in the
Free Theorem kind of way), that the semantics of Ord completely specify
the semantics of Eq, and the only free and continuous way to specify
this is to make == and EQ always agree.
I would (almost) take this conclusion as normative as well.
Dan Weston wrote:
> 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?
Adrian Hey wrote:
Neil Mitchell wrote:
2) What does it do with duplicate elements in the list? I expect it
them. To avoid this, you'd need to use something like fromListWith,
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.
Haskell-Cafe mailing list
Haskell-Cafe mailing list