今まで扱ってきたリスト,例えば

(a b c)

などは,真リストと言われる.真リストとは,cdr部がコンスかnilであるコンスからなるリストである.car部はアトムでもコンスでもnilでもよい.

> (setf alist '(a b c))
(A B C)
> (cdr alist)
(B C)
> (cdr (cdr alist))
(C)
> (cdr (cdr (cdr alist)))
NIL
> (setf (car alist) nil)
NIL
> alist
(NIL B C)

初心者の私は,これまでにサンプルを作成する過程で思いがけず

(a . b)

などという出力に出会ったことがある.そのときは関数の返り値がコンスなのかアトムなのかという意識なしにコーディングした結果であった.処理系がバグッたのかと思ったが,実はこれはドットリストと呼ばれるものである.ドットリストとは,cdr部にアトムをもつコンスを含むリストである.

> (setf blist '(a b))
(A B)
> (setf (cddr blist) 'c)
C
> blist 
(A B . C)

上のblistを図示してみる. このように二つ目のコンスのcdr部にアトムである'c'がある.名前が先なのか表記方法が先なのかはわからないが,上のようにドットリストはコンスのcar部とcdr部をドットで区切って表記される.分かりやすく,一つのコンスからなるドットリストを示してみる.

> (setf clist '(a . b))
(A . B)
> (car clist)
A
> (cdr clist)
B

表記方法を中心に考えてみると,ドットリストの表記に使用されるドットはコンスのcar部とcdr部を分ける線だとイメージできる.実際,真リストもドットを使用した表記が可能で,

> (setf dlist '(a . (b . (c . (d . nil)))))
(A B C D)

などということもできる.Lisp処理系は普通,真リストの表記にドットを使用することはなく,処理系が出力するリストにドットがあれば,そのリストはドットリストである.

コンスには二つのデータ(へのポインタ...まぁ,ポインタもデータか)を格納できる.コンスのcdr部をコンスへのポインタとする(すなわちリスト)ことで,論理的には無限のデータを格納できる.逆に言えばデータが二つなら真リストとする必要がなく,一つのコンスからなるドットリストで足りる.さて,連想リスト(※)とは,各要素がコンスであるリストである.すなわちリストを構成するコンスのcar部がコンスである.連想リストの最も簡単な例として,キーとアトムのペアからなるコンスを要素とするリストがある.

> (setf alist '((a . hoge) (b . fuga) (c . foo)))
((A . HOGE) (B . FUGA) (C . FOO))

このように,キーに対応する値がアトムであるならリストの各要素はドットリストで足りる.キーをもつコンスを取り出す関数としてassocがある.

> (assoc 'a alist)
(A . HOGE)
>(assoc 'd alist)
NIL

指定されたキーがみつからなければ,assocはnilを返す.上の例では最も簡単な連想リストを示すためにその各要素をドットリストとしたが,当然ながら通常のリストとすることもできる(というかこういう例はいままでにも見てきた).

> (setf alist2'((a a1 a2) (b b1 b2) (c c1 c2)))
((A A1 A2) (B B1 B2) (C C1 C2))
> (assoc 'a alist2)
(A A1 A2)

このように,assocは第二引数で指定されたリストの各要素を調べ,car部が第一引数で指定されたキーと一致する要素を返す.第二引数で指定するリストの各要素がリストという前提ということから予想されるように,assocにはキーワード引数としてtest,keyがある.

> (setf alist2 (cons alist2 '(((d) d1 d2))))
(((A A1 A2) (B B1 B2) (C C1 C2)) ((D) D1 D2))
> (assoc 'd alist2)
NIL
> (assoc '(d) alist2)
NIL
> (assoc '(d) alist2 :test #'equal)
((D) D1 D2)

このように,第二引数の各要素はリストであればよいので,キーにはアトムだけでなくリストもありうる.デフォルトではキーの一致はeqlだが,上の最後の式ではキーワードtestでequalに変更している.