copy-list vs. copy-tree

[General Maximus]

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?

[Ramarren]

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)))))

[qbg]

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.

[General Maximus]

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

[wchogg]

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

[General Maximus]

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

That explains it. Thanks