My開発メモ

copy-list と copy-tree はどう違うのか (Common-Lisp)

『On Lisp』はなかなか難しい。特にコードが難しい。
『部分ツリーでの再帰』のところも、よくわからなかった。

どのリストも二分ツリーとして解釈できる．そのため copy-list と copy-tree 等の Common Lisp の関数の組がある．前者はリストを連続構造としてコピーする．リストが部分リストを含むとき，それは連続構造の要素に過ぎないのでコピーされない：

> (setq x ’(a b)
        listx (list x 1))
((A B) 1)

> (eq x (car (copy-list listx)))
T

それとは対照的に，copy-tree はリストをツリーとしてコピーする．部分リストは部分ツリーなので，やはりコピーされる：

> (eq x (car (copy-tree listx)))
NIL

(引用) 4.6 部分ツリーでの再帰 (“On Lisp”)

この箇所、どういう意味なのか、なかなかわからなかった。で、結局こういうことではないかと思う。

前提として、eq関数、equal関数など、以下のようにまとめた(正しいかどうかは自信がない)

(eq A B) -- AとBが、同一オブジェクトである。(メモリ番地も含めてチェックされる)
(eql A B) -- 型、値が同値である。
(equal A B) -- AとBが、同値である。
(= A B) -- AとBが、同値である。型が違っていてもよい。

(参考) 述語 (お気楽 Common Lisp プログラミング入門)

で、『On Lisp』に書かれていた部分を再掲する。

> (setq x ’(a b)
      listx (list x 1))
((A B) 1)

listx を図であらわすと、次のようになる。

これを、以下のようにコピーする。

> (setq lst1 (copy-list listx))
> (setq lst2 (copy-tree listx))

このとき、lst1 を図であらわすと、次のようになる。

copy-list では、listxの基礎部分が新しく作られ、もとのlistxの要素がコピーされる。
そして、その car部は、もとのオブジェクトを参照することになる。
したがって、(car lst1)は、もとのオブジェクトを参照しているので、

(eq x (car lst1))

は T となる。

copy-tree では、listxの全体のセル構造が新しくつくられ、すべての要素がコピーされる。
したがって、(car lst2)は、値は同じでも、新しくつくられたオブジェクトなので、

(eq x (car lst2)) 

は NIL となる。

参考 copy-list, copy-tree, copy-alist

(copy-list)、(copy-alist)、(copy-tree) について、次のサイトにサンプルコードがある。

(参考) Function COPY-TREE (Common Lisp HyperSpec)

サンプルコードは以下。

 (setq object (list (cons 1 "one")
                    (cons 2 (list 'a 'b 'c))))
=>  ((1 . "one") (2 A B C))

(setq object-too object) =>  ((1 . "one") (2 A B C))
 (setq copy-as-list (copy-list object))
 (setq copy-as-alist (copy-alist object))
 (setq copy-as-tree (copy-tree object))
 
 (eq object object-too)             =>  true
 (eq copy-as-tree object)           =>  false
 (eql copy-as-tree object)          =>  false
 (equal copy-as-tree object)        =>  true
 
 (setf (first (cdr (second object))) "a"
       (car (second object)) "two"
       (car object) '(one . 1))     =>  (ONE . 1)
       
 object        =>  ((ONE . 1) ("two" "a" B C))
 object-too    =>  ((ONE . 1) ("two" "a" B C))
 copy-as-list  =>  ((1 . "one") ("two" "a" B C))
 copy-as-alist =>  ((1 . "one") (2 "a" B C))
 copy-as-tree  =>  ((1 . "one") (2 A B C)) 

もとのオブジェクトを変更すると、copy-list したオブジェクトも変更される。
copy-alist の場合も cdr部 が変更される。
copy-treeしたものは、変更されない。

copy-treeは、新しいオブジェクトを作成して、ツリー構造も含めてコピーしている。

copy-alist は、勉強する必要がある。

参考

• 4.6 部分ツリーでの再帰 (“On Lisp”)
• 述語 (お気楽 Common Lisp プログラミング入門)
• Function COPY-TREE (Common Lisp HyperSpec)