From: Pete Humphrey
Subject: CL sort functions
Date:
Message-ID: <1107@tantalum.UUCP>
The Common Lisp definition of the sort function allows it to
destructively modify the sequence, but does it allow it delete items
from the sequence? For example, is the following behavior in Allegro
Common Lisp a bug?
<cl> (setq xxx (list '(1 a) '(0 b) '(1 c) '(0 e) '(1 f)))
((1 A) (0 B) (1 C) (0 E) (1 F))
<cl> (sort xxx #'< :key #'first)
((0 B) (0 E) (1 A) (1 C) (1 F))
<cl> xxx
((1 A) (1 C) (1 F))
Pete Humphrey
····@edsr.eds.com
(505) 345-1863
US Mail:
Pete Humphrey
EDS Research
5951 Jefferson Street N.E.
Albuquerque, New Mexico 87109-3432
····@edsr.eds.com (Pete Humphrey) writes:
>For example, is the following behavior in Allegro
>Common Lisp a bug?
> <cl> (sort xxx #'< :key #'first)
> ((0 B) (0 E) (1 A) (1 C) (1 F))
> <cl> xxx
> ((1 A) (1 C) (1 F))
No, it isn't a bug. The value returned by the sort function contained
>all< the elements of your list. You should have written
(setq xxx (sort xxx #'< :key #'first))
(1 A) was the CAR of your original list, and xxx still pointed at the cons cell with that car, which was now in the middle of the sorted list.
In CLtL (1st version - I don't have a copy of the new one here) I
suppose that it isn't stated as clearly as you might like, for SORT.
In article <····@tantalum.UUCP] ······@edsr.eds.com writes:
>The Common Lisp definition of the sort function allows it to
>destructively modify the sequence, but does it allow it delete items
>from the sequence? For example, is the following behavior in Allegro
>Common Lisp a bug?
>
> <cl] (setq xxx (list '(1 a) '(0 b) '(1 c) '(0 e) '(1 f)))
>
> ((1 A) (0 B) (1 C) (0 E) (1 F))
>
> <cl] (sort xxx #'< :key #'first)
>
> ((0 B) (0 E) (1 A) (1 C) (1 F))
>
> <cl] xxx
>
> ((1 A) (1 C) (1 F))
It didn't delete anything from the list, it just reordered it. The cons
that was and still is XXX's value is now in the middle of the sorted list.
Here's a box-and-pointer diagram of what happened. Before the sort, your
list looked like this:
XXX
|
V
[(1 A)|--]--> [(0 B)|--]--> [(1 C)|--]--> [(0 E)|--]--> [(1 F)|NIL]
After the sort, it looks like this:
XXX
| _________________ _________________
V / V / V
[(1 A)|--]-/ [(0 B)|--]-\ [(1 C)|--]-/ [(0 E)|--]-\ [(1 F)|NIL]
^ ^ \ ^ |
| | \_______________| |
| Returned value /
\__________________________________________________/
The list is still made up of the same conses, and their CARs are all the
same as they were before, but the CDR chaining has been reorganized.
In general, when you use destructive functions on lists you should be
prepared for such rechaining; NREVERSE is another function that typically
rechains CDRs. You should always use
(setq xxx (sort xxx ...))
--
Barry Margolin, Thinking Machines Corp.
······@think.com
{uunet,harvard}!think!barmar
From: Thomas M. Breuel
Subject: Re: CL sort functions
Date:
Message-ID: <9085@life.ai.mit.edu>
|>>The Common Lisp definition of the sort function allows it to
|>>destructively modify the sequence, but does it allow it delete items
|>>from the sequence? For example, is the following behavior in Allegro
|>>Common Lisp a bug?
|>>
|>> <cl] (setq xxx (list '(1 a) '(0 b) '(1 c) '(0 e) '(1 f)))
|>> ((1 A) (0 B) (1 C) (0 E) (1 F))
|>> <cl] (sort xxx #'< :key #'first)
|>> ((0 B) (0 E) (1 A) (1 C) (1 F))
|>> <cl] xxx
|>> ((1 A) (1 C) (1 F))
|>It didn't delete anything from the list, it just reordered it. The cons
|>that was and still is XXX's value is now in the middle of the sorted list.
Note, however, that SORT is also not guaranteed to preserve EQ-ness of the
cons cells making up the original list. I.e., a completely non-destructive
version of SORT would be correct, just as much as a destructive version is.