duplicating and modifying the head of a list of list, in Lisp

Question

I'm learning Lisp. I wish to add a new list to a list of list, say ((1 1 1) (0 0 0)), where the new head of this list collection is computed based on the previous head.

Here's what I tried, in the REPL environment in Slimv with sbcl:

> (defvar *ll* (list (list 1 1 1) (list 0 0 0)))
*LL*
> *ll*
((1 1 1) (0 0 0))
> (push (car *ll*) *ll*)
((1 1 1) (1 1 1) (0 0 0))
> (setf (nth 2 (car *ll*)) 2)
2
> *ll*
((1 1 2) (1 1 2) (0 0 0))

As shown above, I only wanted to modify the last element of the first list, but somehow the last element of the second list was also changed.

I noticed that if instead I push into a brand-new list, then the result is different:

> (defvar *lll* (list (list 1 1 1) (list 0 0 0)))
*LLL*
> (push '(1 1 1) *lll*)
((1 1 1) (1 1 1) (0 0 0))
> (setf (nth 2 (car *lll*)) 2)
2
> *lll*
((1 1 2) (1 1 1) (0 0 0))

I'd like to know what causes these different results, and how to achieve the result that "adds a new list to the list of list, where the new head of resulting list collection is computed based on the previous head." Thanks!

Answer 1

(car *ll*) and (cadr *ll*) are the same list

> (defvar *ll* (list (list 1 1 1) (list 0 0 0)))
*LL*
> *ll*
((1 1 1) (0 0 0))
> (push (car *ll*) *ll*)
((1 1 1) (1 1 1) (0 0 0))
> (setf (nth 2 (car *ll*)) 2)
2
> *ll*
((1 1 2) (1 1 2) (0 0 0))

As shown above, I only wanted to modify the last element of the first list, but somehow the last element of the second list was also changed.

There's only one object there, and you modified it. It's not really any different than if you had some sort of structured data type (and really, what is a cons cell but a structured datatype with just two fields). If you have a list of people, and then you add the first person to the list again, there's still just one person; the person just appears two places in the list. If you change the name of the person, you'll see it in both places. You can actually see the shared structure if you set *print-circle* to t.

CL-USER> (defvar *ll* (list (list 1 1 1) (list 0 0 0)))
*LL*
CL-USER> *ll*
((1 1 1) (0 0 0))
CL-USER> (push (car *ll*) *ll*)
((1 1 1) (1 1 1) (0 0 0))
CL-USER> *ll*
((1 1 1) (1 1 1) (0 0 0))
CL-USER> (setf *print-circle* t)
T
CL-USER> *ll*
(#1=(1 1 1) #1# (0 0 0))

The notation using #1=… and #1# indicates that the same object is the first and second element of the list.

If you want a copy, make a copy

I wish to add a new list to a list of list, say ((1 1 1) (0 0 0)), where the new head of this list collection is computed based on the previous head. …

> (push (car *ll*) *ll*)
((1 1 1) (1 1 1) (0 0 0))

You said that you wanted to add a new list to a list of lists, but you're not adding a new list; you're adding (car *ll*) which is the list you created at the beginning with (list 1 1 1). If you want to copy the list, you'll need to copy it explicitly, e.g., with copy-list:

> (push (copy-list (car *ll*)) *ll*)
((1 1 1) (1 1 1) (0 0 0))

Don't modify literal data!

As an aside, what you're doing in your second code block is actually undefined behavior, since you're modifying the literal list '(1 1 1).

> (defvar *lll* (list (list 1 1 1) (list 0 0 0)))
*LLL*
> (push '(1 1 1) *lll*)            ; '(1 1 1) is literal data.
((1 1 1) (1 1 1) (0 0 0))
> (setf (nth 2 (car *lll*)) 2)     ; (car *lll*) is literal data, and you're modifying it!
2
> *lll*
((1 1 2) (1 1 1) (0 0 0))

See my answer to Unexpected persistence of data for more about why this can be problematic.