引き続き、"Common Lisp: A Gentle Introduction to Symbolic Computation"を読みながら基礎固めをしていく。
Lispというのは"LISt Processing"のことらしいのでリストは重要な位置を占めるのだろう。
Contents
リストの内部構造
内部の構造を理解しておくとリストに対する操作を考えやすくなりそうだ。
連結リスト
Common Lispのリストはいわゆる連結リストの構造をしている。例えば下記のようなリストを考える。
(a b c d)
内部的には各要素はそのデータを指すポインタと次の要素を指すポインタの対となっている。また最後の要素における次の要素を指す部分はNILとなる。
この対となっている箱をコンスセル(cons cell)という。
(a b c d)の内部構造の図
空リスト
空リスト()とNILは等価。リストではあるがコンスセルは含まれない。
リストに対する操作
FIRST, REST
FIRST: リストの最初の要素を返す。
REST: リストの一つ目の要素をのぞいた残りを返す。
上記の内部構造の最初のコンスセルのそれぞれのポインタを返すと考えればよさそうだ。
(a b c d)にそれぞれFIRST、RESTを適用した場合は、
aと(b c d)が返ってくる。
FIRSTと同様にSECOND、THIRD等もある。SECONDはRESTのFIRST、THIRDはRESTのRESTのFIRSTと考えられる。
CAR, CDR
Lispの意味の分からない名前の代表。
"CAR"は"Contents of Addresss portion of Register"の頭文字からきている。
"CDR"は"Contents of Decrement potion of Register"の頭文字からきている。
大昔のLispを動かしていたマシンのregisterの各部のことらしい。
動作としては、CARはFIRSTと同じ。CDRはRESTと同じ。
CARとCDRは合成することができる。
CDRのCARはCADR。
CDRのCDRのCARはCADDR。
4つの合成まで対応しているらしい。パッと見てわかりにくいのだが使っている人はいるのか？
リスト以外をCAR、CDRに入力するとエラーになる。
ただし、NILのCAR、CDRはどちらもNIL。この関係はプログラミングの利便性のためらしいが、今のところ何が便利なのかはわからない。Schemeではエラーらしい。
CONS
"CONS"は"constructure"の略。CONSを使用してコンスセルを作ることができる。
aと(b c d)に対してCONSを適用すると(a b c d)ができる。
リストの最後のコンスセルのCDRはNILなので、aとNILにCONSを適用すると(a)となる。
(a b c d)をCONSで作るには、
aとbとcとdとNILのCONSのCONSのCONSのCONSとすればよい。
CONSとCAR,CDRの関係
上記のようにCARとCDRはリストの最初のコンスセルの二つのポインタを返す。その二つのポインタでコンスセルを作ればもとのリストになるはずだ。
- リストの
CARとCDRにCONSを適用すると元のリストになる。
LIST
CONSだけでリストは作れるが、LISTを使えばもっと楽にリストを作ることができる。a、b、c、dにLISTを適用すると(a b c d)が返ってくる。
LISTP, CONSP
リストかどうか、コンスセルかどうかを判定するpredicatesがある。それぞれLISTP、CONSPである。先に書いたようにリストはコンスセルなのでこれらはほぼ同じ機能である。
唯一の違いはNILに適用した際の挙動。NILのLISTPはTだが、NILのCONSPはNILである。空リスト(=NIL)はリストだがコンスセルはないということか。
まとめ
- リストはコンスセルで構成されている。
- 空リスト
()とNILは等価 CAR,CDR,FIRST,RESTでリストの先頭要素と残りを取り出せる。CONSでコンスセルを作る。- リストの
CARとCDRにCONSを適用すると元のリストになる。 LISTでリストを作る。
コメント