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

[Aaron Denney]

On 2008-03-11, Adrian Hey <ahey at iee.org> wrote:
> Neil Mitchell wrote:
>> Hi
>> 
>>>  (sort [a,b]) in the case we have: (compare a b = EQ)
>>>
>>>  Which of the following 4 possible results are correct/incorrect?
>>>  1- [a,a]
>>>  2- [a,b]
>>>  3- [b,a]
>>>  4- [b,b]
>> 
>> Fortunately the Haskell sort is meant to be stable,
>
> I would have said it is meant to be *correct* first and *efficient*
> second. You're ruling out a whole bunch of possibly more efficient
> and correct sorts on the grounds that they may give observably different
> results for a tiny minority of (IMO broken) Eq/Ord instances.

It's exactly your opinion that these are broken that we're arguing
about.  My view is that they are just equivalence and ordering
relations, not complete equality relations.  Using sortBy, or wrapping
in a newtype with a different ordering instance and then using sort
should be equivalent.

> Wrt to *sortBy* (vs. *sort*), I would be inclined to agree with you.
> I sure hope someone has proven that the (apparently) different sortBy
> implementations provided by ghc,nhc and h98 library report are precisely
> equivalent for all (type legal) function arguments.
>> and sorting is
>> meant to be a permutation, so we happily have the situation where this
>> has a correct answer: 2.
>
>> Anything else is incorrect.
>
> Isn't 3 also a permutation? Why is it incorrect?

Stability --  see "Fortunately the Haskell sort is meant to be stable," above.

>> Adrian: I think its fairly clear we disagree about these things.
>> However, we both understand the others point of view, so I guess its
>> just a question of opinion - and I doubt either of us will change. As
>> such I think any further discussion may just lead to sleep deprivation
>> [1]. I think I'm coming from a more discrete maths/theoretical
>> background while you are coming from a more practical/pragmatist
>> background.
>
> If the "discrete maths/theoretical" POV necessatates to the kind of
> biasing madness of Data.Map/Set (for example) then it *sucks* bigtime
> IMO :-)


> Having tried this approach myself too (with the clone) I can confirm
> that *this way lies madness*, so in future I will not be making
> any effort to define or respect "sane", unambiguous and stable behaviour
> for "insane" Eq/Ord instances for any lib I produce or hack on. Instead
> I will be aiming for correctness and optimal efficiency on the
> assumption that Eq and Ord instances are sensible.

Good.  But sensible only means that the Eq and Ord instances agree, not that
x == y => f x == f y.

-- 
Aaron Denney
-><-