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

Adrian Hey wrote:

Denis Bueno wrote:

...

On Tue, Mar 11, 2008 at 4:01 AM, Adrian Hey wrote:

...

...

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?

Because it is not stable.

The documentation for Data.List.sort says the sort is stable:

"The sort function implements a stable sorting algorithm."

A stable sort respects the order of equal elements as they occur in the input list.

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.

The fact that you can't implement a function to differentiation does not meant the difference is not important. "[b,a]" might cause 500G of file IO which "[a,b]" will not cause. This is not observable within haskell, but is very observable to the user. Stability is a nice property. I don't understand why you are arguing against this so aggressiviely. Jules