inconsistent definition of "sort" (and what about stability?)
Subject: inconsistent definition of "sort" (and what about stability?)
From: Robert Dodier
Date: Sun, 20 Nov 2011 15:02:50 -0700
On 11/19/11, Steve Haflich <smh at franz.com> wrote:
> Stavros Macrakis <macrakis at alum.mit.edu> wrote:
>
> If P(a,b) is not true or false for some a and b, sort signals an error.
>
> From where do you infer this behavior? It is _not_ something about
> cl:stable-sort guaranteed by the ANS (assuming the Maxima call to sort
> has not been rewitten to wrap the predicate to test for this).
Maxima wraps the predicate before calling STABLE-SORT
so that non-Boolean values trigger an error.
> On Sat, Nov 19, 2011 at 20:28, Oliver Kullmann <O.Kullmann at swansea.ac.uk>
> wrote:
>
> Predicate should return true if and only if the first argument is
> strictly less than the second (in some appropriate sense).
>
> (It's sloppy in the sense that "appropriate sense" it not defined.)
>
> "Appropriate sense" here means that sort predicate determines the
> desired ordering. That sense is opaque to and of no concern to sort
> itself.
The spec could avoid the abiguity by saying that P(a, b) returns T iff
b is a successor of a in the sort order.
Come to think of it, the spec could avoid talking about what the
predicate "should" do, and simply say that the result is the order
induced by the predicate (assuming the predicate satisfies the
requirements stated elsewhere, which amount to saying it's a
strict weak order; thanks Oliver).
FWIW
Robert Dodier