inconsistent definition of "sort" (and what about stability?)

On Sat, Nov 19, 2011 at 18:32, Robert Dodier <robert.dodier at gmail.com>wrote:

Comments in line:


>  -- Function: sort (<L>, <P>)
>
>     Sorts a list <L> according to a predicate `P' of two arguments,
>     such that `<P>(<L>[k + 1], <L>[k])' is `false' for any two
>      successive elements.
>

I'm afraid this definition is incorrect.  After all, L= [1,1] is sorted
according to "<=", but P(L[2],L[1]) is true.  And what is the purpose of
saying "any two successive elements" when we already have L[k+1] and L[k]?
Also, "L" is being used in the same sentence to mean two very different
things: the input list and the output list.  All in all, very confusing.
 Why not something simpler like:

    Sorts a list <L> using an ordering function P of two arguments, which
defines a "less than or equals" relation.  More precisely, if P(a,b) and
P(b,a) are both true, then the order of a and b remains the same as in the
input ("stable sort").  Otherwise, a comes before b if P(a,b).

(This also makes the discussion of stable sort below unnecessary.)

 The predicate may be specified as the name
>      of a function or binary infix operator, or as a `lambda'
>      expression.  If specified as the name of an operator, the name is
>     enclosed in "double quotes".
>

Adding an example might help: e.g. "<".


>      The sorted list is returned as a new object; the argument <L> is
>     not modified.  To construct the return value, `sort' makes a
>     shallow copy of the elements of <L>.
>

The doc should mention that it is a shallow copy -- this is pervasive in
Maxima; cf. cons, append, matrix, [], etc. etc.  Anyway, the vast majority
of readers won't know what "shallow copy" means.

     It is assumed the predicate <P> is a strict total order on the
>     elements of <L>.


No, it is assumed that P is total, but not strict -- i.e. it is like <=,
not <.  (Otherwise we wouldn't have to specify stability.)


>  If not, `sort' might run to completion without
>     error, but the result is undefined.  `sort' complains if the
>     predicate evaluates to something other than `true' or `false'.
>

Instead of "complains", how about "gives an error"?  "Complains" could mean
"prints a warning".


>     `sort' is a stable sort: if two elements <x> and <y> are
>     equivalent in the sense that `<P>(<x>, <y>)' and `<P>(<y>, <x>)'
>     are both `false', then the relative order of <x> and <y> in <L> is
>     preserved by `sort'.
>

No, this is incorrect.  If P(x,y) and P(y,x) are both false, then P is not
a total order (strict or otherwise), and all bets are off.


>     `sort (<L>)' is equivalent to `sort (<L>, orderlessp)'.  That is,
>      the default sorting order is ascending, as determined by
>      `orderlessp'.    All Maxima atoms and expressions are comparable
>     under `orderlessp'.
>
>     The predicate `ordergreatp' sorts a list in descending order.  The
>     predicate `ordermagnitudep' sorts Maxima numbers, constant symbols
>     with a numerical value, or expressions which can be evaluated to a
>     constant by magnitude.  All other elements of the list <L> are
>     sorted by `orderlessp'. The predicate `"<"' allows the ordering
>
    by magnitude too, but does not order completely if elements in the
>     list <L> are not comparable under `"<"'.
>

This is misleading -- it implies that "<" uses the same kind of "magnitude"
as "ordermagnitudep".  But it also takes into account the "assume"
database, which ordermagnitudep does not (why not? yes, it is more
expensive if there are non-constants in the list, but simplifies the
semantics).

It is also incorrect: it does not "not order completely" if they are not
comparable, it gives an error:

     sort([a,b,c],"<") => Unable to evaluate predicate

Hope this helps.

          -s