LISPの基本データ構造（コンスセル，連結リスト，連想リスト，属性リスト）

呼び水的初心者アウトプット風LISP記事第二弾．第一弾はこちら．今回は，実行例にCommon Lispの処理系であるSteel Bank Common Lisp (SBCL)を用いており，インストール・実行方法等は既に把握していることを想定しています．

この記事では，下記書籍の3.6で述べられている『table』を利用する方法のうちの 連想リスト（association list） と 属性リスト（property list） について，それらを実現している基本データ構造である コンスセル（cons cells） および 連結リスト（linked list） と併せて述べています．ここでいうtableは，キーと値をセットにして格納したデータ構造を指し，他のプログラミング言語では，辞書型，連想配列，ハッシュテーブルと呼ばれているものに相当します．

Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp by Peter Norvig (1992)

LISPでも今でこそ，ベクタや構造体，ハッシュテーブル，オブジェクトといった，大量・複雑なデータを高速かつ容易に処理するための仕組みが用いられていますが，LISPという名称が『LISt Processor』から生まれているように，配列構造よりもむしろ，リスト構造やリストに関連するデータ構造が伝統的に用いられてきました．これらは今でも，プログラムやデータを構成するための基本要素として用いられています．

コンスセル

コンスセルは，LISP系言語において最も基礎となるデータ構造です（ただし，ClojureやHyはこの構造をもっておらず，連結リストを基礎データ構造としています）．次のボックス記法で示す図のように，二種類の要素を参照できるセルがふたつあり，CAR部，CDR部と呼ばれる組合せ（順序対）で構成されています．

要素のひとつである アトム（atom） は，記号（シンボル）や数値といった，それ以上は分解することができない基本データを指しています．たとえば，CAR部がアトムA，CDR部がアトムBを指し示しているコンスセルは次のようになります．

このコンスセル構造を，LISPプログラムの記法である S式 で表現すると次のようになります（'は(quote ...)の省略形で，関数実行と区別してデータ構造をそのまま示すために用いられています）．ドットで区切って括弧でくくった表現であることから，ドット対（dotted pair） と呼ばれています．

* '(A . B)
(A . B)

LISPの基本関数であるconsはこのドット対を作り出し，car，cdrはそれぞれCAR部，CDR部を取り出します（この例は関数実行であるため，'は用いられていません）．

* (cons 'A 'B)
(A . B)
* (car (cons 'A 'B))
A
* (cdr (cons 'A 'B))
B

各セルは，もうひとつの種類の要素であるコンスセル構造自身を参照できることから，連結リストや連想リストを始めとした，様々なデータ構造を表現することが可能です．

連結リスト

コンスセル構造を用いた代表的なデータ構造が連結リストであり，リストとのみ呼ぶ場合は，単方向の連結リストを指すことがほとんどです．次は，要素A，B，Cが連なっているリストの例です．

これを，consを用いて構成したのが次の実行例です．なお，()は上記の図の3番目のコンスセルの斜線のセルに相当する空リストで，何も参照していないことを表しています．

* (cons 'A (cons 'B (cons 'C '())))
(A B C)

このように，コンスセルによって表現されたリスト構造は，空白区切りのS式表現に自動的に変換されます．これは，ドット対によって構成した場合も同じで，S式では空白区切りの表現そのものを用いることも可能です．

* '(A . (B . (C . ())))
(A B C)
* '(A B C)
(A B C)

LISPでは，プログラム記述のほとんどがリスト構造で表現されることもあって，リストについてはより見やすい表現が導入されています．

ここで，上記の連結リストから先頭の要素であるAを取り出すことを考えると，単純に，先頭のコンスセルのCAR部の参照を取り出せば良いことがわかります．

* (car '(A B C))
A

同じく，先頭の要素を取り除いたリストを得るためには，先頭のコンスセルのCDR部の参照を取り出すことになります．

* (cdr '(A B C))
(B C)

ここで，cdrをもう一度実行すれば，二番目のコンスセルのCDR部の参照を取り出すことになり，要素Cのみのリストが得られます．

* (cdr (cdr '(A B C)))
(C)

更に，consを用いて新しくコンスセルを作り，CAR部がA，CDR部が上記二回のcdr実行で得られた結果を参照するようにすれば，AとCが連なるリストとなります．

* (cons 'A (cdr (cdr '(A B C))))
(A C)

リストはコンスセル構造を用いて再帰的・反復的に構築され，また，各セルがコンスセル構造を参照できることから，リストの要素としてリストを用いることもできます．このためLISPでは，再帰的・反復的な関数処理を用いてリスト処理を行うことが基本となります．

連想リスト

コンスセルはふたつの要素を参照するため，キーと値をセットとしたデータ構造の基本要素としてそのまま用いることができます．次は，果物の名前をキー，果物の金額を値として見立てたコンスセルを3つ構成し，それらをリストとした例です．

* '((APPLE . 120) (ORANGE . 210) (LEMON . 180))
((APPLE . 120) (ORANGE . 210) (LEMON . 180))

このデータ構造は連想リストと呼ばれ，キー，または，値で検索することで，いわゆる辞書型や連想配列といったデータ構造と同じ役割を果たします（歴史的には，辞書型や連想配列よりも早く登場しています）．なお，association listの省略形として『alist』と通称されることがあります．

連想リストを検索する関数は簡単に定義できますが，LISPの多くの仕様や処理系では連想リストを扱う関数が用意されています．次は，連想リストをキーで検索するCommon Lispの関数assoc，値で検索する関数rassocの使用例です（NILは空リスト()と同じ意味であり，また，偽の意味も持ちます）．

* (assoc 'ORANGE '((APPLE . 120) (ORANGE . 210) (LEMON . 180)))
(ORANGE . 210)
* (cdr (assoc 'ORANGE '((APPLE . 120) (ORANGE . 210) (LEMON . 180))))
210
* (assoc 'NASHI '((APPLE . 120) (ORANGE . 210) (LEMON . 180)))
NIL
* (rassoc '180 '((APPLE . 120) (ORANGE . 210) (LEMON . 180)))
(LEMON . 180)
* (car (rassoc '180 '((APPLE . 120) (ORANGE . 210) (LEMON . 180))))
LEMON

なお，Common Lispでは，ふたつの同じ要素数のリストから連想リストを生成する関数pairlis，リストの要素のうち連想リストのキーと同じものを値に置き換える関数sublisがあります．

* (pairlis '(X Y Z) '(10 20 30))
((Z . 30) (Y . 20) (X . 10))
* (sublis (pairlis '(X Y Z) '(10 20 30)) '(X AND Y AND Z))
(10 AND 20 AND 30)

連想リストの利点は，基本データ構造を用いて手軽に作成・利用できることです．欠点は，リストの先頭から順に検索するため，キーと値のセットが大量にある場合，最悪，セットの要素全ての比較が必要となり，検索処理に時間がかかってしまうことです．本格的な辞書型データ構造を扱う場合は，ハッシュテーブルを用いた方法を利用するべきでしょう．

属性リスト

このデータ構造は，Common LispやEmacs Lispなど，ひとつの記号に複数の種類の値を割り当てることができるLISPで用いられているもので，property listの省略形として『plist』と呼ばれることがあります．属性リスト自体は通常の連結リストですが，このリストが記号に結び付けられ，また，連想リストと同じく，キーと値のセットの並びとして表現・利用されているという特徴があります．

次は，連想リストで登場した果物の名前と金額の例と同じセットを，それぞれ異なる記号に設定し，また，値を取り出しているCommon Lispでの実行例です．getは属性リストの値を参照する関数，setfは参照関数と組み合わせて値を変更するための構文，symbol-plistは記号に割り当てられた属性リスト全体を参照する関数です．

* (setf (get 'A 'APPLE) 120)
120
* (setf (get 'B 'ORANGE) 210)
210
* (setf (get 'C 'LEMON) 180)
180
* (get 'B 'ORANGE)
210
* (get 'A 'ORANGE)
NIL
* (symbol-plist 'A)
(APPLE 120)

属性リストの利点は，記号とキーを用いた事実上の表形式のデータ構造であるため，扱うデータ集合によっては連想リストよりも検索が速くなること，目的によってキーと値のセットを分散設定できることがあります．欠点は，属性リストの全ての値をリセットすることが困難であること，値で検索することができないことなどがあります．こちらについてもハッシュテーブル方式に取って代わられていますが，簡単な表データを扱う際には今でも有効でしょう．

備考

記事に関する補足

• ClojureやHaskellのように，コンスセルではなく連結リストを基本データ構造とすること自体は間違いではないのだよな．たとえば，属性リストで用いられている，キーと値を交互に並べる連結リスト方式（交代リストと呼ばれることあり）は，コンスセルによる連想リストと比べた場合，キーや値がマッチした時のセット取り出しが煩雑になるというだけで，それ以外の，コンスセルの使用数や検索時のcar/cdr処理についてはほとんど違いがないという…．

更新履歴

• 2020-11-13：初版公開