Changing Copy of Lists in LISP

Question

In LISP, I have a function that passes a list. I would like to change an element of this list without changing the original list. I usually use copy-list to create a local copy of the list, which I will modify, but this does not seem to work:

 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 been changed to test , although I copied the list to a local variable and changed the local copy. This seems to be a symptom of using nth . If I use one call to car and not call nth again, the function works as expected, and item does not change after the call.

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

I am using Common Lisp.

Answer 1

Short answer: use cl: copy-tree

Most likely, you will want to copy the whole tree copy the tree . A copy made by a list of copies generates only a new "trunk"; you get a new list, but with the same elements. The copied tree will copy the entire cons-tree structure that makes up the tree.

Long answer: list structure versus tree structure

This document describes the background. From HyperSpec:

COPY LIST function

Only the list list structure is copied; The items in the resulting list match the corresponding items in this list.

This glossary element for list structure is important:

List structure n. (list) the set of requirements that make up the list. Note that although the automotive component of each of these minuses is part of the list structure, objects that are elements of the list (i.e. objects that are cars of every minus in the list) are not themselves part of their list structure, even if they are conses, except in the (circular) case where the list actually contains one of its tails as an element. (A list structure list is sometimes unnecessarily called a "top-level list structure" to emphasize that any conses that are elements of a list are not involved.)

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

 CL-USER> (setf *print-circle* t) T CL-USER> (let ((l '((abc) (def)))) (list l (copy-list l))) ;=> ((#1=(ABC) #2=(DEF)) (#1# #2#)) CL-USER> (let ((l '((abc) (def)))) (list l (copy-tree l))) ;=> (((ABC) (DEF)) ((ABC) (DEF))) 

The HyperSpec tab in the copy tree does not refer to the tree structure, but there is a glossary entry:

tree structure . (tree) set of requirements that make up a tree. Please note that while the automotive component of each of these minuses is part of the tree structure, objects that are cars of each of them in the tree themselves are not part of its tree structure, if they are not also conses.

This second sentence is a bit odd, but it probably resides there as a minimally adjusted copy and insertion of a list structure element. See my answer in Defining a Tree Structure in Lisp for a bit more about this.