On Mon, Mar 10, 2008 at 9:08 PM, Jonathan Cast <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> <http://www.eyrie.org/~zednenem/> _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
