[Haskell-cafe] Re: (flawed?) benchmark : sort
dave at zednenem.com
Mon Mar 10 22:14:02 EDT 2008
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
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>
More information about the Haskell-Cafe