Adrian Hey wrote:
Denis Bueno wrote:
On Tue, Mar 11, 2008 at 4:01 AM, Adrian Hey <[EMAIL PROTECTED]> 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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
