Am I abusing SORT? It sure ain't working for me....

According to the CLHS in re SORT:

"[the sort] Predicate should return true if and only if the first argument is strictly less than the second (in some appropriate sense). If the first argument is greater than or equal to the second (in the appropriate sense), then the predicate should return false."

I am trying to sort a list of the nodes in DAG where kids know their parents. My only requirement on the sort result is that no node precede any of its ancestors (its parent or its parent's parent or etc). Two siblings, for example, can appear in any order.

My predicate correctly returns T if arg1 is an ascendant of arg2. Otherwise it returns nil. So nil means either that arg2 is an ascendant of arg1, or that neither is an ascendant of the other. My reading of the above CLHS excerpt tells me SORT is fine with that.

My nodes ain't getting sorted correctly. In at least one case, a kid comes out before an ascendant (its parent, as it happens).

I observe that the two never get compared directly. I realize that would not always be necessary, but printing out all the comparisons I find only two out of some two or three dozen that test out to be True. So that is not a lot of information by which to sort quite a few things (have not counted them up, but around twenty).

I am about to start whittling the thing down to where I have a literal list and some simpler code to play with so I can easily test in other Lisps, but I thought I would drop by here to find out if I am missing something subtle about sorting.

kenny
.

Relevant Pages

  • Re: Name For - Functions that indicate order?
    ... earlier in a sequence and false if not. ... At the moment the function is called CompareItem, I am trying to come up ... Predicate used to sort entire vector". ...
    (comp.programming)
  • Re: randomize-list
    ... implementations of sort can either ... If the key and predicate always return, ... and does not require predicate or key to be consistent: ...
    (comp.lang.lisp)
  • Re: does sort always sort vectors in place?
    ... this is accomplished by permuting the elements in ... ??>> (setf v (sort v predicate)) ... Subtle but crucial difference. ...
    (comp.lang.lisp)
  • Re: does sort always sort vectors in place?
    ... this is accomplished by permuting the elements in ... ??>> (setf v (sort v predicate)) ... Subtle but crucial difference. ...
    (comp.lang.lisp)
  • Re: does sort always sort vectors in place?
    ... On 26/04/2010 11:19, Captain Obvious wrote: ... this is accomplished by permuting the elements in ... ??>> (setf v (sort v predicate)) ...
    (comp.lang.lisp)