I have noticed that the Common Lisp sort functions, SORT and
STABLE-SORT, doesn't produce a correct partial order, when the
predicate represents certain partial orders.
For example, let the even numbers be ordered in the usual way, but let
the odd numbers be incomparable with respect to each other and even
numbers. This can be represented by the predicate:
(DEFUN TEST-PARTIAL-ORDER-PRED (A B)
(COND ((ODDP A) NIL)
((ODDP B) NIL)
(T (< A B))
)
)
Now
(SORT LST #'TEST-PARTIAL-ORDER-PRED)
produces:
LST Result
(0 1 2) (0 1 2)
(0 2 1) (0 2 1)
(1 0 2) (1 0 2)
(1 2 0) (1 0 2)
(2 1 0) (2 1 0) <-- Wrong !
(2 0 1) (0 2 1)
This fails whenever two even numbers are separated by an odd number,
unless the even numbers are already ordered.
I'm sure there are good reasons for this limitation, but CLtL2 doesn't
seem to be clear on this point. Is this implementation dependent ?
Does X3J13 clarify this issue ?
Ingemar Hulthage
Associate Professor
Computational Organization Design
University of Southern California
Los Angeles, CA 90089-0021
········@usc.edu (email)
(213) 740-4044 (voice)
(213) 740-9732 (fax)
In article <...> ········@torsk.usc.edu (Ingemar Hulthage) writes:
>
> I have noticed that the Common Lisp sort functions, SORT and
> STABLE-SORT, doesn't produce a correct partial order, when the
> predicate represents certain partial orders.
>
> I'm sure there are good reasons for this limitation, but CLtL2 doesn't
> seem to be clear on this point. Is this implementation dependent ?
> Does X3J13 clarify this issue ?
From CLtL2, p. 408:
If the :key and predicate functions always return, then the sorting
operation will always terminate, producing a sequence containing the
same elements as the original sequence (that is, the result is a
permutation of sequence). This is guaranteed even if the predicate DOES
NOT really consistently represent a TOTAL ORDER (in which case the
elements will be SCRAMBLED IN SOME UNPREDICTABLE WAY, but no element
will be lost).
This seems to clearly indicate that sort is not required to produce
anything reasonable for a partial order predicate.
--
________________________________________________________________________
Thomas A. Russ, Senior Research Scientist ···@isi.edu
USC/Information Sciences Institute WWW: http://isi.edu
4676 Admiralty Way, Marina del Rey, CA 90292 (310) 822-1511x775