Writing GNU Emacs Extensions

Destructive List Operations

So far, all the list operations we've looked at have been non-destructive. For instance, when you cons an object onto an existing list, the result is a brand new cons cell whose cdr points to the unaltered old list. Any other objects or variables that refer to the old list are unaffected. Similarly, append works by making a brand new list, creating as many new cons cells as necessary to hold the elements of the lists in its arguments. It cannot make the last cdr of x point directly to y, or the last cdr of y point directly to z, because the nil pointer at the end would be changed. x and y could no longer be used in their original forms. Instead append makes an unnamed copy of those lists as shown in Figure 6-5. Note that the value of z need not be copied; append always uses its last argument directly.^[25]

Figure 6-5. The append function does not alter its arguments.

Here's what the non-destructiveness of append means in Lisp code:

(setq x '(a b c))
(setq y '(d e f))
(setq z '(g h i))
(append x y z) ⇒ (a b c d e f g h i)

Because append does not destructively modify its arguments, these three variables continue to have their old values:

x ⇒ (a b c)
y ⇒ (d e f)
z ⇒ (g h i)

But if destructive modification were used, then each variable would refer to some part of a single, long cons chain made when the three shorter cons chains are strung together as shown in Figure 6-6 ...