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

[Dan Weston]

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

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?
> 
> 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
>>
>>
> 
>