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

[Adrian Hey]

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