The difference is subtle and not visible on the first view, but
APPEND makes copies of all of its arguments, except of its last argument. For the last argument the elements are copied by the recursive function from the y-list. The result is a list that is completely independent from the structure of the original input lists. This sounds complicated, but I will show what that means by a few simple examples.
David Touretzky's and your code, both seem to produce the same result, here the list (1 2 3 4) stored in the z variable:
Code: Select all
(defparameter x (list 1 2 3))
(defparameter y (list 2 3 4))
(defparameter z (my-union x y))
x => (1 2 3)
y => (2 3 4)
z => (1 2 3 4)
The invisible difference is that with David Touretzky's code the z-list contains copies of the elements in the original y-list, while with your code the z-list contains a direct reference (a pointer) to the original y-list:
Code: Select all
(defun my-union (x y)
(cond ((null x) y) ; <- y returns a pointer to the first cons cell of the y-list
((member (car x) y)
(my-union (cdr x) y))
(t (cons (car x)
(my-union (cdr x) y)))))
This difference becomes visible as soon as you try to modify elements in the z-list that come from the y-list.
With David Touretzky's code:
Code: Select all
(setf (fourth z) 5)
x => (1 2 3)
y => (2 3 4)
z => (1 2 3 5) ; <- fourth element modified (desired effect)
With your code:
Code: Select all
(setf (fourth z) 5)
x => (1 2 3)
y => (2 3 5) ; <- third element modified (unwanted effect)
z => (1 2 3 5) ; <- fourth element modified (desired effect)
The y-list gets modified because the z-list contains a pointer to the y-list and not independent copies of the elements in the y-list. The last three elements in the z-list
are the elements of the y-list, not copies of the elements. Changing one of these elements in one list also changes the element in the other list:
Code: Select all
(setf (first y) 0)
x => (1 2 3)
y => (0 3 5) ; <- first element modified (desired effect)
z => (1 0 3 5) ; <- second element modified (unwanted effect)
You can avoid this unwanted behaviour by using
COPY-LIST like this:
Code: Select all
(defun my-union (x y)
(cond ((null x) (copy-list y))
((member (car x) y)
(my-union (cdr x) y))
(t (cons (car x)
(my-union (cdr x) y)))))
Now your function works like David Touretzky's code.
I assume that David Touretzky did not want to discuss the subtle differences how "copy by value" and "copy by reference" work with Common Lisp lists because teaching the basics is already complicated enough and
APPEND was already introduced in the book.
Practical Common Lisp, chapter 12:
List Processing explains the difference in more detail but if you're still fighting with the basics save these links for later.
As a rule of thumb one can say that Common Lisp generally passes arguments by reference (pointers) and does
not make copies from complex data structures unless explicitely told to do so by functions like
COPY-LIST. The behaviour of
APPEND is a very rare exception.
BTW, I've learned Common Lisp from the Touretzky book, too.
- edgar