copy-list vs. copy-tree

Discussion of Common Lisp
Post Reply
General Maximus
Posts: 3
Joined: Wed Jul 16, 2008 10:01 am

copy-list vs. copy-tree

Post by General Maximus » Wed Jul 16, 2008 10:09 am

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
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: copy-list vs. copy-tree

Post by ramarren » Wed Jul 16, 2008 11:23 am

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

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

Re: copy-list vs. copy-tree

Post by qbg » Wed Jul 16, 2008 11:32 am

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
Posts: 3
Joined: Wed Jul 16, 2008 10:01 am

Re: copy-list vs. copy-tree

Post by General Maximus » Thu Jul 17, 2008 5:24 am

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

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

Re: copy-list vs. copy-tree

Post by wchogg » Thu Jul 17, 2008 6:47 am

Right.
http://www.gigamonkeys.com/book/beyond- ... cells.html gives a nice pictoral explanation.

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

Re: copy-list vs. copy-tree

Post by General Maximus » Thu Jul 17, 2008 10:25 am

wchogg wrote:Right.
http://www.gigamonkeys.com/book/beyond- ... cells.html gives a nice pictoral explanation.
That explains it. Thanks :)

Post Reply