LISP very simple list question

Question

Im learning lisp and im pretty new at this so i was wondering...

if i do this:

(defparameter *list-1* (list 1 2))
(defparameter *list-2* (list 2 3))
(defparameter *list-3* (append *list-1* *list-2*))

And then

(setf (first *list-2*) 1)
*list-3*

I will get (1 2 1 4)

I know this is because the append is going to "save resources" and create a new list for the first chunk, but will actually just point to the second chunk, coz if i do:

(setf (first *list-1*) 0)
*list-3*

I will get (1 2 1 4) instade of the more logical (0 2 1 4)

So my question is, what other cases are like this in lisp, how do you black belt lispers know how to deal with this stuff that is not intuitive or consistent?

Answer 1

The append function has to make a copy of its first argument, to avoid modifying existing data structures. As a result, you now have two list segments that look like (1 2 ...), but they're part of different lists.

In general, any list can be the tail of any other list, but you can't have a single list object that serves as the head of multiple lists.

Answer 2

Um, primarily we learn how it works, so that what we imagine isn't consistent makes sense.

What you need to do is find some of the old-fashioned block and pointer diagrams, which I can't easily draw, but let's figure it out.

After the first defparameter, you've got list-1, which is

(1 . 2 . nil)

in dot notation; list-2 is

(2 . 3 . nil)

Answer 3

You have to think of lists in terms of cons cells. When you define list 1 and list 2, it is like:

(defparameter *list-1* (cons 1 (cons 2 nil)))
(defparameter *list-2* (cons 2 (cons 3 nil)))

Then, when you append:

(defparameter *list-3* (cons 1 (cons 2 *list-2*)))

Basically, a cons cell consists of two parts; a value (the car), and a pointer (the cdr). Append is defined to not change the first list, so that is copied, but then the last cdr (normally nil) is changed to point at the second list, not a copy of the second list. If you were willing to destroy the first list, you would use nconc.

Try this:

(defparameter *list-3* (nconc *list-1* *list-2*))

Then observe the value of *list-1*, it is (1 2 2 3), just like *list-3*.

The general rule is that the non-destructive functions (append) won't destroy existing data, while the destructive functions (nconc) will. What a future destructive function does ((setf cdr)), though, is not the responsibility of the first non-destructive function.

Answer 4

One defensive tactic is to avoid sharing structure.

(defparameter *list-3* (append *list-1* *list-2* '()))

or

(defparameter *list-3* (append *list-1* (copy-list *list-2*)))

Now the structure of the new *list-3* is all new, and modifications to *list-3* won't affect *list-2* and vice versa.

Answer 5

So my question is, what other cases are like this in lisp, how do you black belt lispers know how to deal with this stuff that is not intuitive or consistent?

By reading the fine manual? Hyperpsec explicitly states:

[...] the list structure of each of lists except the last is copied. The last argument is not copied; it becomes the cdr of the final dotted pair of the concatenation of the preceding lists, or is returned directly if there are no preceding non-empty lists.

Answer 6

quote:

So my question is, what other cases are like this in lisp, how do you black belt lispers know how to deal with this stuff that is not intuitive or consistent?

I think that you are a bit harsh here with a subject that is quite a bit larger than you imagine. Lists are a rather elaborate concept in Lisp, and you need to understand that this is not some simple array. The standard provides a lot of functions to manipulate lists in every way. What you want in this case is:

(concatenate 'list *list-1* *list-2*)

So, why is there also append? Well, if you can omit copying the last list, and all symbols involved still return the correct data, this can be a significant performance boost in both calculating time and memory footprint. append is especially useful in a functional programming style which doesn't use side effects.

In lieu of further explanation about cons cells, destructive vs. nondestructive functions etc., I'll point you to a nice introduction: Practical Common Lisp, Ch. 12, and for a complete reference, the Common Lisp Hyperspec, look at Chapters 14 and 17.