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


So, looking at the hyperspec,

If the key and predicate always return, then the sorting operation
will always terminate, producing a sequence containing the same
elements as 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). If the key consistently returns meaningful keys, and the
predicate does reflect some total ordering criterion on those keys,
then the elements of the sorted-sequence will be properly sorted
according to that ordering.

What you would *like* the hyperpsec to say (for your purposes) is that
if the predicate represents a partial order, that the returned
sequence will respect that partial order --- in other words, that you
can use sort to do topological sort. Unfortunately, it doesn't say
that. According to the spec, if the predicate I give is a partial
order, it looks like just returning the sequence in a random order is
conforming behavior. Your predicate is a partial order, so you can
portably expect nothing except that you get back a new sequence
containing the same elements.

I agree with Jens Axel Søgaard's first suggestion in that I believe
what you want is a topological sort. The good news is it's O(n), not
O(n log n). The bad news is that you probably get to right it
yourself. The good news is it's not really hard.

(Side note: I think this is the "right" specification for sort, in
that the optimal algorithms for sort with a full ordering do not
automatically respect partial orderings (as you're observing). It
would be amusing to formalize this, if I had more time.)

Cheers,

rif
.

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: Go Fish game in Lisp
    ... >> I have a function for shuffling a list into random order. ... However SORT *is* guaranteed to terminate as long as the predicate ... producing a sequence containing the same ...
    (comp.lang.lisp)
  • Re: Am I abusing SORT? It sure aint working for me....
    ... sequence will respect that partial order --- in other words, ... can use sort to do topological sort. ... if the predicate I give is a partial ...
    (comp.lang.lisp)
  • Re: How Best to Randomize a List?
    ... It wouldn't work with bubble sort -- ... the poor thing would terminate only by accident. ... predicate is consistent, that makes them do what we want given this ... result of sorting a sequence by a random predicate will produce all ...
    (comp.lang.lisp)
  • Re: Am I abusing SORT? It sure aint working for me....
    ... sequence will respect that partial order --- in other words, ... can use sort to do topological sort. ... if the predicate I give is a partial ...
    (comp.lang.lisp)