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

[Jonathan Cast]

On 10 Mar 2008, at 4:00 AM, 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).

Data.Map is implicitly using such an Ord instance behind the scenes,  
and I think it has to to maintain its own invariants.  If I take the  
`union' of two maps that take the same key to different values, I  
have to decide which value to use, even if every Ord instance  
supplied by my clients is 100% Adrian-compliant.

jcc