roy@phri.UUCP (Roy Smith) (08/04/89)
I'm trying to figure out how the sort function works in KCL, but I think I'm getting hung up on what "Common Lisp: The Language" means when it says in section 14.5: "The sequence is destructively sorted". I took "destructively sorted" to mean "sorted in-place", but it looks like it really means "trashed, but a sorted copy is returned". For example: >(setq foo '(1 3 9 4 -2 0 9)) (1 3 9 4 -2 0 9) >foo (1 3 9 4 -2 0 9) >(sort foo #'>) (9 9 4 3 1 0 -2) >foo (1 0 -2) Sort returns a sorted list as its value, but the argument gets trashed. Is this really the way it's supposed to work? Do I have to do (setq foo (sort foo #'>)) to get it to work? -- Roy Smith, Public Health Research Institute 455 First Avenue, New York, NY 10016 {att,philabs,cmcl2,rutgers,hombre}!phri!roy -or- roy@alanine.phri.nyu.edu "The connector is the network"
shiffman%basselope@Sun.COM (Hank Shiffman) (08/05/89)
In article <3916@phri.UUCP> roy@phri.UUCP (Roy Smith) writes: > I'm trying to figure out how the sort function works in KCL, but I >think I'm getting hung up on what "Common Lisp: The Language" means when it >says in section 14.5: "The sequence is destructively sorted". I took >"destructively sorted" to mean "sorted in-place", but it looks like it >really means "trashed, but a sorted copy is returned". For example: > >>(setq foo '(1 3 9 4 -2 0 9)) >(1 3 9 4 -2 0 9) > >>foo >(1 3 9 4 -2 0 9) > >>(sort foo #'>) >(9 9 4 3 1 0 -2) > >>foo >(1 0 -2) > > Sort returns a sorted list as its value, but the argument gets >trashed. Is this really the way it's supposed to work? Do I have to do >(setq foo (sort foo #'>)) to get it to work? Yes, this is exactly the way it's supposed to work. Notice that in your example, FOO points to a CONS whose CAR is 1 both before and after the sort. When CLtl says that a function on a list operates destructively, it means that the CONS cells of the original list may be reused. FOO still points to the CONS cell which has a CAR of 1. It's just not the first CONS cell in the sorted list. Keep in mind that since SORT is a function, (sort foo #'>) causes sort to be handled the *value of FOO*, not the symbol itself. So SORT (as it's currently defined) couldn't put sorted list back into FOO even if it wanted to. -- Hank Shiffman (415) 336-4658 Marketing Technical Specialist Software Engineering Technologies ...!sun!shiffman Sun Microsystems, Inc. shiffman@Sun.com Zippy sez: Gee, I feel kind of LIGHT in the head now, knowing I can't make my satellite dish PAYMENTS!
hoey@ai.etl.army.mil (Dan Hoey) (08/05/89)
In article <119605@sun.Eng.Sun.COM> shiffman@sun.UUCP (Hank Shiffman) writes: >> >>>foo >>(1 3 9 4 -2 0 9) >> >>>(sort foo #'>) >>(9 9 4 3 1 0 -2) >> >>>foo >>(1 0 -2) ... >Keep in mind that since SORT is a function, (sort foo #'>) causes sort >to be handled the *value of FOO*, not the symbol itself. So SORT (as >it's currently defined) couldn't put sorted list back into FOO even if >it wanted to. Actually, you can make this work by using the cons cell you are given as the head of the list. For example, (defun my-sort (original &rest sortargs) (let ((sorted (apply #'sort original sortargs))) (unless (eq original sorted) (rotatef (car sorted) (car original)) (setf (cdr (do ((s sorted (cdr s))) ((eq (cdr s) original) s))) sorted) (rotatef (cdr original) (cdr sorted)))) original) doesn't CONS but does give its argument the value of the sorted list. This, however, requires that SORT return a list of which its argument is a tail, which is not explicitly required by CLtL. Dan
len@synthesis.Synthesis.COM (Len Lattanzi) (08/05/89)
In article <3916@phri.UUCP> roy@phri.UUCP (Roy Smith) writes:
:>(setq foo '(1 3 9 4 -2 0 9))
:(1 3 9 4 -2 0 9)
:
:>foo
:(1 3 9 4 -2 0 9)
:
:>(sort foo #'>)
Consider that you're handing to sort a cons-cell that looks like
[1 . (3 9 4 -2 0 9)]
Sort can change the cdr but no matter what foo will still point to
this cons-cell and in this case the car will not be smashed by sort.
:(9 9 4 3 1 0 -2)
:
:>foo
:(1 0 -2)
:
: Sort returns a sorted list as its value, but the argument gets
:trashed. Is this really the way it's supposed to work? Do I have to do
:(setq foo (sort foo #'>)) to get it to work?
Yes
:--
:Roy Smith, Public Health Research Institute
:455 First Avenue, New York, NY 10016
:{att,philabs,cmcl2,rutgers,hombre}!phri!roy -or- roy@alanine.phri.nyu.edu
:"The connector is the network"
\
Len Lattanzi ({ames,pyramid,decwrl}!mips!synthesis!len) <len@Synthesis.com>
Synthesis Software Solutions, Inc. The RISC Software Company
I would have put a disclaimer here but I already posted the article.