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

[Dan Weston]

 > 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
>