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

I agree, I view == as some kind of equivalence relation in Haskell, and not a congruence relation (which would force x==y => f x == f y). Of course, the Haskell type system isn't strong enough to enforce anything more than it being a function returning a boolean. -- Lennart On Wed, Mar 12, 2008 at 12:55 AM, Aaron Denney wrote:

On 2008-03-11, Adrian Hey 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 -><-

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe