Let's play “Spot the bug”. After running this code, what is the value
(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), 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, 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
(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
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
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.
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
(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, 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.
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.
 I'm assuming a definition
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))))