Changing copies of lists in LISP

Question

In LISP, I have a function that is passed a list. I would like to change an element of this list without changing the original list. Normally, I would use copy-list to create the local copy of the list which I will change, but this doesn't seem to be working:

CL-USER> (defun test (item)
    (let ((copy (copy-list item)))
         (setf (nth 0 (nth 0 (nth 0 copy))) t)
         (print item)
         (print copy)))

CL-USER> (defparameter item `(((NIL NIL) (NIL NIL) (NIL NIL))
                     ((NIL NIL NIL) (NIL NIL NIL))
                     ((3 3) (NIL NIL))))

CL-USER> (test item)
(((T NIL) (NIL NIL) (NIL NIL)) ((NIL NIL NIL) (NIL NIL NIL)) ((3 3) (NIL NIL))) 
(((T NIL) (NIL NIL) (NIL NIL)) ((NIL NIL NIL) (NIL NIL NIL)) ((3 3) (NIL NIL))) 
(((T NIL) (NIL NIL) (NIL NIL)) ((NIL NIL NIL) (NIL NIL NIL)) ((3 3) (NIL NIL)))
CL-USER> item
(((T NIL) (NIL NIL) (NIL NIL)) ((NIL NIL NIL) (NIL NIL NIL)) ((3 3) (NIL NIL)))

As you can see, the value of item was changed by test even though I copied the list into a local variable and changed the local copy. This seems to be a symptom of using nth. If I use a single call of car rather than the repeated call to nth, the function works as expected and the item is unchanged after the call.

Why does nth behave like this and how can I continue to use nth without altering the value passed to test?

I am using Common Lisp.

Answer 1

Short answer: use cl:copy-tree

You probably want to copy the whole tree with copy-tree. The copy made by copy-list only generates new "backbone"; you get a new list, but with the same elements. Copy-tree will copy all the cons-tree structure that makes up the tree.

Long answer: list structure vs. tree structure

The background here is referenced in the documentation. From the HyperSpec:

Function COPY-LIST

Only the list structure of list is copied; the elements of the resulting list are the same as the corresponding elements of the given list.

That glossary entry for list structure is important:

list structure n. (of a list) the set of conses that make up the list. Note that while the car component of each such cons is part of the list structure, the objects that are elements of the list (i.e., the objects that are the cars of each cons in the list) are not themselves part of its list structure, even if they are conses, except in the (circular) case where the list actually contains one of its tails as an element. (The list structure of a list is sometimes redundantly referred to as its "top-level list structure" in order to emphasize that any conses that are elements of the list are not involved.)

As a very simple example, we can exploit the fact that *print-circle* will show us common substructure:

CL-USER> (setf *print-circle* t)
T

CL-USER> (let ((l '((a b c) (d e f))))
           (list l (copy-list l)))
;=> ((#1=(A B C) #2=(D E F)) (#1# #2#))

CL-USER> (let ((l '((a b c) (d e f))))
           (list l (copy-tree l)))
;=> (((A B C) (D E F)) ((A B C) (D E F)))

The HyperSpec entry on copy-tree doesn't link to tree structure, but there is a glossary entry:

tree structure n. (of a tree) the set of conses that make up the tree. Note that while the car component of each such cons is part of the tree structure, the objects that are the cars of each cons in the tree are not themselves part of its tree structure unless they are also conses.

That second sentence is a bit strange, but it's probably just in there as a minimally adjusted copy and paste of the list structure entry. See my answer to Definition of tree structure in Lisp for a bit more about that.