【Common Lisp】連想リスト、循環リスト、ドットリスト

リストはLispの基本ですが、単なるリストではなく色々なリストがあります。ドットリスト、循環リスト、連想リストについてまとめます。

ドットリスト

以下に２つの例を挙げます。

普通のリスト：

CL-USER> (cons 1 (cons 2 (cons 3 nil)))
(1 2 3)

終端がnilでないリスト：

CL-USER> (cons 1 (cons 2 3))
(1 2 . 3)

かっこの中にドットがあるのが分かります。ドットが使われているのは、リストの表記で隠蔽されない生のコンスセルがそこにあることを表現しています。上の普通のリストでは、nilが省略されて、コンスセルが見えなくなっているだけなのです。
このように終端がnilではないリストのことを、ドットリストと言います。

通常のリストを、ドットリストの表現で書くこともできます。

CL-USER> '(1 . (2 . (3 . nil)))
(1 2 3)

対となる２つの値を表現するためによく用いられるそうです。

CL-USER> (defparameter *pair* '(1 . 2))
*PAIR*
CL-USER> (car *pair*)
1
CL-USER> (cdr *pair*)
2

簡単に値を取り出すことができます。

循環リスト

このように、終端が自分自身を指しているようなリストのことを循環リストと言います。
循環リストを実装してみようと思いますが、その前に以下のコマンドを実行しておきます。

(setf *print-circle* t)

これをやっておかないと、表示が無限ループに陥って大変なことになるらしいです。

CL-USER> (defparameter foo (list 1 2 3))
FOO
CL-USER> (setf (cdddr foo) foo)
#1=(1 2 3 . #1#)

なお、ここではlistコマンドを使ってリストを作っていますが、このように後々に変更するリストは '(1 2 3) のように作るのではなくlistコマンドを使って作るのが作法となっているようです。

連想リスト（association list, alist）

他言語でいう辞書みたいなもので、キーと値をセットにしてリストに保管します。

CL-USER> (defparameter *drink-order* '((bill . double-espresso)
                                       (lisa . small-drip-cofee)
                                       (john . medium-latte)))
*DRINK-ORDER*

assoc

assoc関数は連想リストから、キーを指定してキーと値を取り出します。最初にヒットした要素が取り出されることに注意。

CL-USER> (assoc 'lisa *drink-order*)
(LISA . SMALL-DRIP-COFEE)
CL-USER> (push '(lisa . large-mocha-with-whipped-cream) *drink-order*)
((LISA . LARGE-MOCHA-WITH-WHIPPED-CREAM) (BILL . DOUBLE-ESPRESSO)
 (LISA . SMALL-DRIP-COFEE) (JOHN . MEDIUM-LATTE))
CL-USER> (assoc 'lisa *drink-order*)
(LISA . LARGE-MOCHA-WITH-WHIPPED-CREAM)

参考

コンラッド・バルスキ（2013）「Land of Lisp」 川合史郎訳 オライリー・ジャパン