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

ajb@spamcop.net wrote:

G'day all.

Adrian Hey wrote:

...

...

This might be a reasonable thing to say about *sortBy*, but not sort as the ordering of equal elements should not be observable (for any correct instance of Ord). It should be impossible to implement a function which can discriminate between [a,a],[a,b],[b,a],[b,b] if compare a b = EQ.

Nonsense. Consider a Schwartzian transform wrapper:

data OrdWrap k v = OrdWrap k v

instance (Ord k) => Ord (OrdWrap k v) where compare (OrdWrap k1 v1) (OrdWrap k2 v2) = OrdWrap k1 k2

I take it you mean something like .. instance Ord k => Ord (OrdWrap k v) where compare (OrdWrap k1 v1) (OrdWrap k2 v2) = compare k1 k2 Where's the Eq instance for OrdWrap? This may or may not satisfy the law: (compare a b) = EQ implies (a == b) = True. I think everbody agrees about that, but I can't tell from the code you've posted if it does in this case. What's disputed is whether or not this law should hold: (a == b) = True implies a = b Again, I can't tell if it does or not in this case, but I assume the point of your post is that it doesn't. AFAICT the report is ambiguous about this, or at least the non-intutive equality semantics are not at all clear to me from what I can see in the Eq class definition (para 6.3.1). I think an the absence of any clear and *explicit* statement to the contrary people are entitled to assume this law is mandatory for all (correct) Eq instances.

It would be incorrect (and not sane) for sort [a,b] to return [a,a] in this case, though a case could be made that either [a,b] or [b,a] make sense.

Quoting Jules Bean :

...

Stability is a nice property. I don't understand why you are arguing against this so aggressiviely.

Stability is an occasionally very useful property. However, if there is a tradeoff between stability and performance, I'd prefer it if the library didn't choose for me.

Well I hope you or anyone else hasn't used Data.Map or with OrdWrap keys because if so it's likely that the code has either been broken in the past, or is broken now (not sure which). But the equality semantics some people seem to want seem to me like a very good way to guarantee that similar bugs and ambiguities will occur all over the place, now and forever. Regards -- Adrian Hey