## copy-list vs. copy-tree

Discussion of Common Lisp

### copy-list vs. copy-tree

I've been reading Paul Graham's ANSI Common Lisp. I've just reached chapter 3, and I'm already loving the language.

I've got a little bit of trouble with some code I saw in the book. In chapter 3 he mentions that all lists can be thought of as trees and demonstrates a piece of code which returns a copy of the tree you pass in. The function is called our-copy-tree, and looks like this :
Code: Select all
`(defun our-copy-tree (tr)  (if (atom tr)      tr    (cons (our-copy-tree (car tr))     (our-copy-tree (cdr tr)))))`

Before that, Graham wrote this function :
Code: Select all
`(defun our-copy-list (lst)  (if (atom lst)      lst    (cons (car lst) (our-copy-list (cdr lst)))))`

I understand that both these functions are present in the CL library as copy-list and copy-tree respectively. What I don't understand is the difference between these two functions.

I can see that copy-tree is doubly recursive while copy-list is singly recursive, but ultimately both these functions seem to give me the same output, no matter how complicated a list I pass to them.

What is the difference between our-copy-list and our-copy-tree?
General Maximus

Posts: 3
Joined: Wed Jul 16, 2008 10:01 am

### Re: copy-list vs. copy-tree

General Maximus wrote:What is the difference between our-copy-list and our-copy-tree?

Remeber, Common Lisp doesn't have lists as such, only conses, which can be thought of as pairs of pointers, each of which can point to either an atom, or a list. List and trees can be easily built from those.

So, our-copy-list copies lists, and our-copy-tree trees. That is, in the first case, only top level conses are copied, and in the second case all conses are copied. In both cases all atoms are the same atoms. The reason why they seem to give the same output while printed is that you cannot see object identity in printed output. You can check object identity using eq, like this:
Code: Select all
`(let ((tree (list (list 'a))))  (let ((copied-by-list (our-copy-list tree))        (copied-by-tree (out-copy-tree tree)))    (list (eq (car tree) (car copied-by-list))          (eq (car tree) (car copied-by-tree)))))`
ramarren

Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

### Re: copy-list vs. copy-tree

Another way to see the difference:
Code: Select all
`CL-USER 3 > (let* ((original (list (list 'a) 'c))                   (copy-list (copy-list original))                   (copy-tree (copy-tree original)))              (setf (caar original) 'b)              (print copy-list)              (print copy-tree)              (values))((B) C) ((A) C)`

Notice how copy-list shares the '(a) cons with the original so when it was modified, copy-list was modified too.
qbg

Posts: 64
Joined: Mon Jun 30, 2008 1:05 pm
Location: Minnesota

### Re: copy-list vs. copy-tree

So what you mean to say is, even though both of them are logically the same list, but they have different internal representations?
General Maximus

Posts: 3
Joined: Wed Jul 16, 2008 10:01 am

### Re: copy-list vs. copy-tree

wchogg

Posts: 5
Joined: Thu Jul 03, 2008 2:39 pm

### Re: copy-list vs. copy-tree

wchogg wrote:Right.
http://www.gigamonkeys.com/book/beyond-lists-other-uses-for-cons-cells.html gives a nice pictoral explanation.

That explains it. Thanks
General Maximus

Posts: 3
Joined: Wed Jul 16, 2008 10:01 am