> 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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
