プログラミングを頑張る日記

プログラミングを勉強して、ハッカーになろう

Common Lispを頑張る(52)

「実践Common Lisp」やっていきます。
第13章はコンスセルについての章です。

リストと木

コンスセルから構成される構造を木として扱うことは自然なことだそう。
コンスセルの集まりはリストとしてか木として扱われますが、その扱いの違いは
関数が要素を見つけだす時のコンスセルの探索の仕方の違いだそうです。
リスト関数はコンスセルの集まりを、1つ目のコンスセルから始めてcdrが参照している先を
nilに到達するまで到っていくと。あるコンスセルのcarが参照しているオブジェクトは
そのリストに含まれる要素ですが、そのオブジェクトが別のコンスセルなら
それは注目しているリスト構造には含まれません。別のリストの先頭ということになるそう。
木構造を扱う関数の場合、carとcdrの両方を、参照先がコンスセルでなくなるまで辿ります。
要素とみなされるのは、辿ってみつけたアトム全てです。

ツリー向けの関数についてもいくつか説明がありますが割愛。
しかしツリー向け関数で破壊的な関数、使える自信がまるでありません。おっかない。

集合

どんなリストでも集合として扱え、集合論的な操作をするための関数もいくつかあるそうです。
とはいえ集合が大きくなるほど非効率になることを肝に命じろ、ということです。
でも記述が簡単になるのは確かで、小さな集合に対してなら効率がよいかも、ということで
一回書いてみてボトルネックになっていたら集合のリストをハッシュテーブルとか
ビットベクタに書き換えてみるということがオススメされています。

集合を組み立てるにはadjoinだそう。これは1つのアイテムと集合を表すリストを引数に、
オリジナルの集合の全要素と引数として与えたアイテムを含む集合を表すリストを返すそう。
集合に既にアイテムが含まれていたら足してはだめなので、まず集合のリストをスキャンします。
そして含まれていなければ新しいコンスセル(オリジナル+アイテム)を生成して返すということです。
含まれていればオリジナルをそのまま返すと。
これは非破壊的ですが、オリジナルを更新してくれるpushnewというマクロもあるそう。

集合にあるアイテムが含まれているかどうかはmember,member-if,member-if-notが使え、
それらはリスト専用のfind,find-if,find-if-notだと思ってしまってよさそう。
アイテムが存在すれば、指定したアイテムを含むコンスセルを返してくれるそうです。
しなければ予想通り(?)、nilが返ってきます。

他の集合論的な関数をざっと。それぞれ2つのリストを引数にとります。
intersection...2つの集合の和を返す
union...2つの集合の積を返す
set-difference...1つ目の引数における2つ目の引数の補集合を返す
set-exclusive-or...2つの集合の対象差を返す
上記全てにnをつけたリサイクルバージョンがあるそうです。
あと便利そうな、subsetpという引数の1つ目のリストが2つ目のリストの
部分集合であるときに真を返す関数が最後に紹介されました。

大学生のころ何となくとった論理学の授業は楽しかったし、
今仕事ではほとんどSQLしかやっていないので集合の話は嫌いじゃないです。
とばしぎみなのは、この章が終わったら「Land of Lisp」に帰ろうと企んでいるからです。
あと5ページばかりありますが。
しかし今回一回も実際に書いていません。ダメダメな感じ。
だけど気にしない、おやすみなさい。