List Mutation Public Service Announcement

Let's play “Spot the bug”. After running this code, what is the value of a?

(define a (list 1 2 3))
(reverse! a)

Too easy? Well, if you said the list (3 2 1) you are wrong. Well, not entirely, it could be (3 2 1), but odds are you probably see a value more like (1)[1], and this is perfectly allowed.

This trips up new lispers on a semi-regular basis, and we had similar questions twice just the other day on #emacs.

Lisp Linked Lists are not one object

If you came to Lisp from Python, or some other non-functional language with builtin lists, you probably expect lists to be a single object. This is not the case.

Lists in Lisp and in functional languages are a single type[2], but they are a sum type made up of two kinds of objects: pairs and an end of list (nil) object. In Haskell, the list type could be expressed like

data List a = Nil | Cons a (List a)

Aside from a pretty recursive definition for pedagogical purposes, this representation has some practical purpose. It allows you to write list processing functions which share the tails of lists, as in the traditional definition of append.

(define (append xs ys)
  (if (null? xs)
      ys
      (cons (car xs)
            (append (cdr xs) ys))))

But since it is a sum type, it is not always simple to treat a list as a single mutable object.

What to do with nil?

Now, let's try and write a version of append that mutates the prefix list. If xs is a pair, we have two cases: either the tail is a nil or a pair. If the tail of xs is nil, then we add on ys to the end by mutating the tail to point to ys. If it is a pair, we keep going down the list. At this point the definition looks like

(define (append! xs ys)
  (if (null? xs)
      ???
      (if (null? (cdr xs)) ;; end of list
          (set-cdr! xs ys)
          (append! (cdr xs) ys))))

But what do we do when xs is nil? We can't mutate it, because there is nothing to change: nil has no fields. Even if we could append ys to the end of nil, we would run into trouble since there is only one null object, and now every list would have ys appended to the end.

Since we cannot mutate xs in that case, we might decide to return ys directly, but then we've introduced an issue similar to the one in the original example, namely, you need to pay attention to the output of procedures that mutate lists.[3]

The improved version of append! that always returns an appended list looks something more like

(define (append! xs ys)
  (define (add-to-end! xs)
    (if (null? (cdr xs))
        (set-cdr! xs ys)
        (add-to-end! (cdr xs))))
  (cond ((null? xs) ys)
        (else
          (add-to-end! xs)
          xs)))

So, returning to our original example, if you wanted a to be the list (3 2 1), the correct thing to do is

(define a (list 1 2 3))
(set! a (reverse! a))

Don't mutate lists

I'm a functional imperialist; I'm not ashamed to admit that. If you want my advice, it's simply to never mutate lists (or strings, but for different reasons). Mutate vectors, hashtables etc. with my blessing[4], but not lists, since they shared around faster than the latest cat video on Youtube.

But if you have to, if you really have to, then always use the return value of those list mutation procedures, and write your own to work similarly.

Cheers to tali713 and Fuco on #emacs for giving this a once-over.

Footnotes

[1]Lisp doesn't actually even have a list type, it's a collective fiction we impose on a certain structure of pairs, but we'll ignore that.

[2]Although, if you want to, you can use my libraries of semi-persistent vectors and other functional datastructures.

[3]A fancy way of saying this is that many of those procedures are “linear update”.

[4] I'm assuming a definition of reverse! that travells down the list swapping the links, similar to

(define (reverse! xs)
  (define (swap-cdrs! prev xs)
    (if (null? xs)
        prev
        (let ((next (cdr xs)))
          (set-cdr! xs prev)
          (swap-cdrs! xs next))))
  (cond ((null? xs) '())
        (else (swap-cdrs! '() xs))))