[erlang-bugs] lists:usort bug 1

[Hans Bolinder]

[Matthias Lang:]
> > [Lev Walkin:]
> > >         usort(Fun, List1) -> List2
> ...
> 
> > >        ordering function Fun... Fun(A, B) should return true if 
> > >        A comes before B in the ordering, false  otherwise.
> ...
> > > Contradicts description "should return true if A comes before B in the 
> > > ordering, false otherwise".
> 
> > Note that it is assumed by sort/2, usort/2, merge/3, and umerge/3 that
> > the fun is an "ordering function". Neither </2 nor >/2 is an ordering
> > function.
> 
> Your answer confuses me. You're not explicitly disagreeing with the
> bug report, but it seems like you implicitly are.

I could have been more explicit when explaining that the
counterexamples were bogus since the funs are no ordering functions.
Thanks for pointing it out.

If a given fun fails to be an ordering function, the results of the
sort and merge functions are not well defined, and actually changed in
R9C (STDLIB 1.12.3, I think), as pointed out by Peter Lund. BTW, I
erroneously referred to a ticket in R9B when replying to Peter's mail.
The correct ticket, OTP-4517 (which isn't mentioned in the release
notes) is about an optimization that happened to change the behaviour
for funs that don't define a total ordering.

> I think '=<'/2 is an ordering function. If it isn't, why not?

It is an ordering function; it is antisymmetric, transitive, and total. 

The phrase "A comes before B in the ordering" dates back to 1999, when
sort/2 was introduced. It was suggested in

   http://www1.erlang.org/pipermail/erlang-bugs/2008-August/000929.html

to change it to "should return true if A compares less than or equal
to B in the ordering, false otherwise", and I now think that is a good
idea. 

It probably won't hurt to mention '=<'/2 as an example of an ordering
function as well, and to point out that '<'/2 is not an ordering
function (it is not total). 

Best regards,

Hans Bolinder, Erlang/OTP team, Ericsson