実践Common Lispを読む 第12章〜第13章
陰に潜むPractical Common Lisp
こんにちは。
今回はリスト特集で13章まで読みました。
これを読む前、真っ暗な公園で、遠くのほうで打ち上げ花火をしながらキャーキャーわめくリア充集団（おそらく許可も何もとっていない）を眺めながらブランコでワンキャップの日本酒を飲んでいました。
リア充集団が近づいてきても威勢よくぶらぶらとブランコを漕いでいたら「あのひとやばくない？」みたいなことを大声で言っていました。聞こえてるっちゅうねん。
なんだか憂鬱で帰ってきてからもウィスキーを炭酸で割って１対１くらいのハイボールを飲んでます。夜の果てへ旅したい。
そういえば明日は参院選ですが、政治と野球の話は喧嘩の元なのでやめておきます。
第12章 リスト処理：やつらがLISPと呼ぶ理由
リストを使うべき時とそうでない時を区別すべきだ
＊リストなんてない
スプーンボーイ：リストを曲げようとしちゃだめだ。そんなことできない。そうじゃなくてただ、真実を見ようとするんだよ。
ネオ：真実？
スプーンボーイ：リストなんてない。
ネオ：リストがない？
スプーンボーイ：そうすればリストを曲げるんじゃないって分かる。自分のことなんだ。
マトリックスにインスパイアされたセリフらしい。
http://www.imdb.com/title/tt0133093/quotes
https://www.youtube.com/watch?v=uAXtO5dMqEI
リストは幻想である。
それはコンスセルと呼ばれる値のペアであり、関数CONSによって作られる。
CONSは２つの引数を取り、それら２つの値を保持する新しいコンスセルを返す。
コンスセルにアクセスするために使われる関数はそれぞれCARとCDRと呼ばれる。
(car (cons 1 2)) -> 1 (cdr (cons 1 2)) -> 2
CARもCDRもSETF可能。
(defparameter *cons* (cons 1 2)) *cons* -> (1 . 2) (setf (car *cons*) 10) -> (10 . 2)
コンスセルに含まれる値はどんな種類のオブジェクトへの参照でも構わない。
コンスセルの仕組みは単方向リンクリストと呼ばれる仕組みで、Lisp固有のものではない。けれど、Lisp以外でこれを使っている言語はほとんど存在しない。
コンスセルは図を見たほうが早い。
早い？
リストとして扱うときにはCARやCDRじゃなくても、FIRST、RESTなんてのもある
(defparameter *list* (list 1 2 3 4)) (first *list*) -> 1 (rest *list*) -> (2 3 4) (first (rest *list*)) -> 2
リストはいろいろなデータが階層化されているような表現に向いている
＊関数プログラミングとリスト
関数プログラミングの真髄は、与えられた引数のみに依存して演算を行う副作用を持たない関数のみでプログラムが構成されることにある。
関数プログラミングの利点はプログラムの理解が容易になること。
Common Lispのリスト操作関数の多くはほとんど関数的にかかれている。
＊「破壊的」な操作
「破壊的」な操作は、2種類あり、副作用が目的である操作と、引数のコンスセルを使いまわし（リサイクル）する操作とがある。
「破壊的」な操作の例として共有している構造を変更する関数などが考えられる。
(defparameter *list-1* (list 1 2)) (defparameter *list-2* (list 3 4)) ;引数に含まれる全ての要素を含む新しいリストを返す関数APPEND ;この場合には、*list-1*をコピーしたものと*list-2*をコンスセルで結合して*list-3*を作っているので、APPENDは破壊的ではなく関数的で、リストの構造を共有している。 (defparameter *list-3* (append *list-1* *list-2*)) ;値を見る *list-1* -> (1 2) *list-2* -> (3 4) *list-3* -> (1 2 3 4) ;*list-2*を変更 (setf (first *list-2*) 0) *list-2* -> (0 4);意図した変更 *list-3* -> (1 2 0 4) ;意図しない変更
リサイクルな関数が安全に使える場合は、オリジナルが不要になる場合だけだ。
例えば非破壊的関数REVERSEと破壊的NREVERSEがある。REVERSEは新たにリストを作るため、setfしなければいけない。NREVERSEはその必要がない。
多くのリサイクルな関数はNがつくだけだが、そうでないものとして
NCONS(APPEND関数のリサイクルな場合)やDELETE(REMOVEに対応する)などがある。
＊リサイクルな関数と構造共有の組み合わせ
破壊的な操作はやっかいなので、イディオムっぽく使われることが多い。
;ゼロから始まるn個の数値を持つリスト ;リストは関数の内部で生成されるので安全 (defun upto (max) (let ((result nil)) (dotimes (i max) (push i result)) (nreverse result))) CL-USER> (upto 10) (0 1 2 3 4 5 6 7 8 9) ;値を置き換える ;この場合も、fooが他のリストと共有している場合、そちらに影響を与えることに注意 (setf foo (delete nil foo))
また、SORT、STABLE-SORT、MERGEもリサイクルな関数であることに注意。
CL-USER> (defparameter *list* (list 1 2 3 4)) *LIST* CL-USER> (sort *list* #'<) (1 2 3 4) CL-USER> *list* (1 2 3 4) ;本では返り値が(4)になっているけど、やってみたら破壊されてない！！！
本と結果が違う不思議。自動的にCOPY-LISTされているのかなあ
＊リスト操作関数
リストの要素を呼び出すとき、FIRSTのほかにSECONDからTENTHまで、あるいはインデックスとリストを引数にとるNTHを使う。同じようにNTHCDRでは、CDRをn回してくれる。
(nthcdr 0)はオリジナルそのまま。
CARとCDRの合成関数もよく見かける。
(caar list) = (car (car list)) (cadadr list) = (car (cdr (car (cdr list))))
でもいまではそこまで頻繁に使われないらしい。
リスト操作の関数を抜粋
LAST,BUTLAST,NBUTLAST,LDIFF,TALIP,LIST*,MAKE-LIST,REVAPPEND,NRECONC,CONSP,ATOM,LISTP,NULL
＊マッピング
関数的なスタイルとして高階関数の利用がある。
Common Lispではリスト専用の6つのマッピング関数が存在する。
MAPCARはMAPそっくりな関数。戻り値が必ずリスト。
MAPLISTはMAPCARに似ているが、関数に渡されるのがリストの要素でなくコンスセル
MAPCANとMAPCONはMAPCARとMAPLISTが新しくリストを生成するのに対して、NCONSみたいにつなぎ合わせる。
MAPCとMAPLは関数に見えるが制御構文、最初のリスト引数をそのまま返す。つまり、マップされる関数が何かしら意味のある副作用を伴う場合に使う。
第13章 リストを超えて：コンスセルの別用途
Common Lispにはコンスセルから構成されるデータ構造を木や集合、ルックアップテーブルとして扱うための関数も用意されている。
＊木
リスト関数と木関数の違いを見るにはCOPY-LISTとCOPY-TREEの違いを見れば分かる。COPY-LISTは構造だけコピーする。木を前提とする関数としてはSUBSTITEの代わりにSUBSTがある。
＊集合
集合は非効率的。集合を組み立てるにはADJOIN関数を使う。集合にあるアイテムが含まれるかはMEMBER関数とその仲間によってテストできる。他にはINTERSECTIONやUNION、SET-DEFFERENCE、SET-EXCLUSIVE-ORなどがある。
＊ルックアップテーブル
コンスセルをベースとしたテーブルとしては、連想リストと属性リストがある。
連想リストはキーと値を対応させるデータ構造で、逆方向の参照もサポートしている。連想リストは実際にはコンスセルになっているリストでしかない。
例えば、((A . 1) (B . 2) (C . 3))のような。
連想リストを扱う関数の主役はASSOC。コンスセルのCARとキーが一致するものがあれば最初のものを返し、なけえればNILを返す。
対応するキーには、ASSOCを呼び出した結果をそのままCDRすれば値が取れる。
(cdr (assoc 'a' ((a . 1)(b . 2)(c . 3)))) ->1
ASSOCは前の方から読むから、後のリストを隠蔽できる。
連想リストの前に新しくペアを追加するには、CONSCONSしなくてはならないが、ACONSを使えば便利。
(cons (cons 'new-key 'new-value) alist) ;同じ意味 (acons 'new-key 'new-value alist) ;あるいはsetfかpushする (setf alist (acons 'new-key 'new-value)) (push (cons 'new-key 'new-value) alist)
COPY-ALIST関数は木構造全体の複製ではなく、リスト構造を構成するコンスセルだけを複製し、加えてそれらのコンスセルのCARが直接参照しているコンスセルの複製を行う。
最後にPAIRLIS関数の紹介。
CL-USER> (pairlis '(a b c) '(1 2 3)) ((C . 3) (B . 2) (A . 1))
もうひとつのルックアップテーブルは属性リストplist。plistでは、setfやgetfやremfを使う。あるいは同一の属性リストから複数の属性を取り出したいときにはGET-PROPERTIESを使う。
属性リストとシンボル。どんなシンボルオブジェクトにも専用の属性リストがあってそのシンボルについての情報を格納するために使うことができる。属性リストはSYMBOL-PLISTで取得できる。でもGET関数のほうが使うと思う。
(get 'symbol 'key) = (getf (symbol-plist 'symbol) 'key) ;あるいはsetf (setf (get 'some-symbol 'my-key) "information")
シンボルの属性リストからある属性を取り除きたければREMFするかREMPROPする。
＊DESTRUCTURING-BIND
DESTRUCTURING-BINDマクロはリストをスライスする。
(destructuring-bind (parameter*) list body-form*)
parameter*にはいろいろ使える。
(destructuring-bind (x (y1 y2) z) (list 1 (list 2 20) 3) (list :x x :y1 y1 :y2 y2 :z z)) ->(:X 1 :Y1 2 :Y2 20 :Z 3) (destructuring-bind (&key x y z) (list :z 1 :y 2 :x 3) (list :x x :y y :z z)) ->(:X 3 :Y 2 :Z 1)
&wholeパラメータは31章に出てくるから復習することpp.158
＊まとめ
リストやMAPCARがこんなに後の章で出てくるというのは驚き。でも関数プログラミングに関する説明がやや少なめなのが気になる。SORT関数の謎。
13章でも知らない関数とかたくさん出てきたけどそんなに使うんだろうか。あまりに詳しく書かれてちょっとヒく。
次回はファイルの出入力と実践編です。
あとはてな記法で括弧がたくさん重なると注釈になる問題が以下のエントリで解決された。
はてな記法で脚注のエスケープ方法 - あずまや
)(すればよいとのこと
