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

[David Menendez]

On Mon, Mar 10, 2008 at 9:08 PM, Jonathan Cast
<jonathanccast at fastmail.fm> wrote:
> On 10 Mar 2008, at 4:00 AM, Adrian Hey wrote:
>
>  > 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.

I think Adrian is just arguing that a == b should imply f a == f b,
for all definable f, in which case it doesn't *matter* which of two
equal elements you choose, because there's no semantic difference.

(Actually, it's probably not desirable to require it for *all*
definable functions, since an implementation might define e.g. an
unsafe function that does pointer comparisons. We'd probably also
exclude functions using a private, "internal" interface that exposes
implementation details.)

I like that property, and it bugs me when I have to use a datatype
whose Eq instance doesn't have it (either because (==) throws away
information or because the type exposes non-semantic information).

So, if a == b, then sort [a,b] could return [a,a], [a,b], [b,a], or
[b,b] at will, because there wouldn't be any way to distinguish those
results in Haskell.

This might have performance implications. You might have a case where
a and b are equal, but have difference performance characteristics. I
don't know what, if anything, is the best way to deal with that.

This discussion feels like it should have a wiki page.

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>