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

[Luke Palmer]

On Mon, Mar 10, 2008 at 11:00 AM, Adrian Hey <ahey at iee.org> 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).

It could be.  I actually don't know what Haskell specifies here.  If a
type has an Eq instance and x == y, must x and y be observationally
equivalent?  Or is it reasonable to allow some wiggle room?  I'd say
(==) definitely has to be an equivalence relation, but beyond that,
it's open to the implementor, since if an algorithm only depends on
(Eq a), it can't tell the difference between observational equality
and any other equivalence relation.  But that's just one argument ("by
example", in a way).  That is, an argument that this is hopelessly
broken isn't trivial, it needs to be defended.

There is nonetheless a need to handle duplicates gracefully, that is
keeping a count won't cut it, because of sortBy.

Luke