copy-list vs. copy-tree
Posted: 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 :
Before that, Graham wrote this function :
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?
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)))))
Code: Select all
(defun our-copy-list (lst)
(if (atom lst)
lst
(cons (car lst) (our-copy-list (cdr lst)))))
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?