On Mon, Mar 10, 2008 at 9:08 PM, Jonathan Cast
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