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

[Adrian Hey]

ajb at 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 <jules at jellybean.co.uk>:
> 
>> 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