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

Jules Bean jules at jellybean.co.uk
Wed Mar 12 09:56:05 EDT 2008


Adrian Hey wrote:
> Denis Bueno wrote:
>> On Tue, Mar 11, 2008 at 4:01 AM, Adrian Hey <ahey at iee.org> 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


More information about the Haskell-Cafe mailing list