2018-12-16 A simple tip on using destructive functions

This is something fairly obvious to every seasoned Lisp programmer, but let’s not forget that there are novices, too.

Many Elisp functions are noted to be “destructive”, which means that they can change their arguments. For instance, if you want to sort a list, you may use the sort function, which is said to modify its argument by side effects (this is exactly what “destructive” means). This does not necessarily mean, however, that after executing (sort some-list), the variable some-list will magically contain a sorted version of it previous self! Let’s consider two examples.

(setq some-list '(1 3 2))
(sort some-list #'<)
some-list

After evaluating the above code, some-list is bound to (1 2 3), i.e., the sorted version, and hence you might think that this is always going to be the case.

Wrong.

Let’s look at this code.

(setq some-list '(3 1 2))
(sort some-list #'<)
some-list

See? Now some-list is just (3).

What is going on here?

Well, in order to understand what happens, we will use the famous cons cell diagrams, found in so many books on Lisp.

Remember that each cons cell contains two “slots”: car and cdr. A list is simply a chain of cons cells whose cars contain (more precisely: point to) values held in the list, and cdrs point to the next cons cell in the chain.

Hence, the list in our first example looks like this.

some-list
    |
    V
 +-A---+-----+   +-B---+-----+   +-C---+-----+
 |  1  |  ------>|  3  |  ------>|  2  |     |
 +-----+-----+   +-----+-----+   +-----+-----+

(An empty slot means nil, of course.)

After the first sort, cons cell A’s cdr is modified to point at C, C’s cdr points at B, and B’s cdr is set to nil. Since some-list still points to A (as we did not assign anything else to this variable), our list looks like this:

some-list
    |     +-------------------------+
    |     |                         |
    V     |                         V
 +-A---+--|--+   +-B---+-----+   +-C---+-----+
 |  1  |  |  |   |  3  |     |   |  2  |  |  |
 +-----+-----+   +-----+-----+   +-----+--|--+
		   ^                      |
		   |                      |
		   +----------------------+

Let’s consider now the second example. We start with this:

some-list
    |
    V
 +-A---+-----+   +-B---+-----+   +-C---+-----+
 |  3  |  ------>|  1  |  ------>|  2  |     |
 +-----+-----+   +-----+-----+   +-----+-----+

and after sorting, our cons cells look like this:

some-list
    |
    |     +-------------------------------+
    |     |                               |
    V     V                               |
 +-A---+-----+   +-B---+-----+   +-C---+--|--+
 |  3  |     |   |  1  |  ------>|  2  |  |  |
 +-----+-----+   +-----+-----+   +-----+-----+

See what happened? Since some-list points at A now, and A’s cdr is nil, we get (3) as some-list.

So, what we should do about it? It turns out that sort returns “the sorted sequence”, which means cons cell B. Therefore, if we want some-list to be sorted, we should say this instead.

(setq some-list '(3 1 2))
(setq some-list (sort some-list #'<))
some-list

And of course, the same goes for other destructive functions, like nreverse or cl-delete.

(You might also look at my earlier post about destructive functions and comments to that post.)

CategoryEnglish, CategoryBlog, CategoryEmacs