Previous: Setcdr, Up: Modifying Lists [Contents][Index]
Here are some functions that rearrange lists “destructively” by modifying the CDRs of their component cons cells. We call these functions “destructive” because they chew up the original lists passed to them as arguments, to produce a new list that is the returned value.
This function returns a list containing all the elements of lists.
Unlike append
(see Building Lists), the lists are
not copied. Instead, the last CDR of each of the
lists is changed to refer to the following list. The last of the
lists is not altered. For example:
(setq x '(1 2 3)) ⇒ (1 2 3)
(nconc x '(4 5)) ⇒ (1 2 3 4 5)
x ⇒ (1 2 3 4 5)
Since the last argument of nconc
is not itself modified, it is
reasonable to use a constant list, such as '(4 5)
, as in the
above example. For the same reason, the last argument need not be a
list:
(setq x '(1 2 3)) ⇒ (1 2 3)
(nconc x 'z) ⇒ (1 2 3 . z)
x ⇒ (1 2 3 . z)
A common pitfall is to use a quoted constant list as a non-last
argument to nconc
. If you do this, your program will change
each time you run it! Here is what happens:
(defun add-foo (x) ; We want this function to add
(nconc '(foo) x)) ; foo
to the front of its arg.
(symbol-function 'add-foo) ⇒ (lambda (x) (nconc (quote (foo)) x))
(setq xx (add-foo '(1 2))) ; It seems to work.
⇒ (foo 1 2)
(setq xy (add-foo '(3 4))) ; What happened?
⇒ (foo 1 2 3 4)
(eq xx xy) ⇒ t
(symbol-function 'add-foo) ⇒ (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
This function reverses the order of the elements of list.
Unlike reverse
, nreverse
alters its argument by reversing
the CDRs in the cons cells forming the list. The cons cell that
used to be the last one in list becomes the first cell of the
value.
For example:
(setq x '(1 2 3 4)) ⇒ (1 2 3 4)
x ⇒ (1 2 3 4) (nreverse x) ⇒ (4 3 2 1)
;; The cell that was first is now last.
x
⇒ (1)
To avoid confusion, we usually store the result of nreverse
back in the same variable which held the original list:
(setq x (nreverse x))
Here is the nreverse
of our favorite example, (a b c)
,
presented graphically:
Original list head: Reversed list: ------------- ------------- ------------ | car | cdr | | car | cdr | | car | cdr | | a | nil |<-- | b | o |<-- | c | o | | | | | | | | | | | | | | ------------- | --------- | - | -------- | - | | | | ------------- ------------
This function sorts list stably, though destructively, and returns the sorted list. It compares elements using predicate. A stable sort is one in which elements with equal sort keys maintain their relative order before and after the sort. Stability is important when successive sorts are used to order elements according to different criteria.
The argument predicate must be a function that accepts two
arguments. It is called with two elements of list. To get an
increasing order sort, the predicate should return t
if the
first element is “less than” the second, or nil
if not.
The destructive aspect of sort
is that it rearranges the cons
cells forming list by changing CDRs. A nondestructive sort
function would create new cons cells to store the elements in their
sorted order. If you wish to make a sorted copy without destroying the
original, copy it first with copy-sequence
and then sort.
Sorting does not change the CARs of the cons cells in list;
the cons cell that originally contained the element a
in
list still has a
in its CAR after sorting, but it now
appears in a different position in the list due to the change of
CDRs. For example:
(setq nums '(1 3 2 6 5 4 0)) ⇒ (1 3 2 6 5 4 0)
(sort nums '<) ⇒ (0 1 2 3 4 5 6)
nums ⇒ (1 2 3 4 5 6)
Note that the list in nums
no longer contains 0; this is the same
cons cell that it was before, but it is no longer the first one in the
list. Don’t assume a variable that formerly held the argument now holds
the entire sorted list! Instead, save the result of sort
and use
that. Most often we store the result back into the variable that held
the original list:
(setq nums (sort nums '<))
See Sorting, for more functions that perform sorting.
See documentation
in Accessing Documentation, for a
useful example of sort
.
Previous: Setcdr, Up: Modifying Lists [Contents][Index]