[Haskell-cafe] Re: (flawed?) benchmark : sort
Adrian Hey
ahey at iee.org
Tue Mar 11 12:20:16 EDT 2008
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.
So really I think the docs have this backwards. It's sortBy that
implements a stable sort (assuming a suitably sane comparison function
I guess) and apparently sort is whatever you get from (sortBy compare).
But this is unduly restrictive on possible correct sort implementations
IMO.
Regards
--
Adrian Hey
More information about the Haskell-Cafe
mailing list