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, relinking their cons cells to form a new list that is the returned value.
delq, in Sets And Lists, for another function
that modifies cons cells.
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
nconcis 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)
However, the other arguments (all but the last) must be lists.
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)) ;
footo 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
nreversealters 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 cons cell of the value.
For example:(setq x '(a b c)) ⇒ (a b c) x ⇒ (a b c) (nreverse x) ⇒ (c b a) ;; The cons cell that was first is now last. x ⇒ (a)
To avoid confusion, we usually store the result of
nreverseback in the same variable which held the original list:(setq x (nreverse x))
Here is the
nreverseof 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 non-
nilif the first element is “less than” the second, or
The comparison function predicate must give reliable results for any given pair of arguments, at least within a single call to
sort. It must be antisymmetric; that is, if a is less than b, b must not be less than a. It must be transitive—that is, if a is less than b, and b is less than c, then a must be less than c. If you use a comparison function which does not meet these requirements, the result of
The destructive aspect of
sortis 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-sequenceand then sort.
Sorting does not change the cars of the cons cells in list; the cons cell that originally contained the element
ain list still has
ain 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)
Warning: Note that the list in
numsno 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
sortand use that. Most often we store the result back into the variable that held the original list:(setq nums (sort nums '<))