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]

The append function does not alter its arguments.

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 ...

Get Writing GNU Emacs Extensions now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.