2007-06-25
■ 連想リストを扱う
問題
連想リストを使うメリットは何なのか？ 連想リストを扱う一連の手続きはどのようなものがあるのか？
説明
連想リスト(associative list, alist)はLispで非常によく使われるデータ構造で、キーと値のペアのリストからなるデータ構造です。通常はキーをユニークにしておいて、それに対応する値を格納するために使います。
((guido . "Guido van Rossum") (matz . "Yukihiro Matsumoto") (larry . "Larry Wall"))
たとえば上のデータは（プログラミング言語作者の名前からなる）連想リストです。
連想リストはハッシュテーブルのように使うことができますが、ハッシュテーブルとは異なる性質を持ちます。
- ルックアップにO(n)の時間が必要
- キーに新しい値をセットするときに破壊的変更を避けられる
- 値からキーを引くことができる
連想リストではキーを探すのにリニアサーチしか一般に方法がないので、ルックアップには連想リストの長さに比例した時間がかかります。従って非常にたくさんのキーと値のペアを連想リストで持つのは効率が悪く、そのような目的ではハッシュテーブルの使用を検討したほうがよいでしょう。
キーに値をセットする際、破壊的変更を避けられるというのは非常に重要な性質です。連想リストを扱う手続きは一般に最初に見つかったキーのペアを返すので、同一のキーのペアがあれば先頭にあるほうが優先されます。つまりリストの先頭にペアを追加しておくと、同じキーを持つペアを隠すことができるということです。
(define alist1 '((foo . 1) (bar . 2))) (define alist2 `((bar . 0) ,@alist1))
上の連想リストalist1、alist2は構造を共有していますが、alist1のbarは2、alist1のbarは0であるように見えます。
alist2 alist1
+---+---+ +---+---+ +---+---+
| . | --------->| . | --------->| . | / |
+-|-+---+ +-|-+---+ +-|-+---+
| | |
+---+---+ +---+---+ +---+---+
| . | 0 | | . | 1 | | . | 2 |
+-|-+---+ +-|-+---+ +-|-+---+
| | |
bar foo bar
データを破壊的変更すると予想もしなかったところにその影響がでて、潰すのが難しいバグの原因になることがよくありますが、連想リストをうまく使うとそのような問題の発生を防止できるというわけです。
連想リストを扱う手続き
連想リストの構築にはconsかacons、あるいは上のalist2の例のようにquasiquoteでテンプレートを指定して組み立てるのが簡単です。連想リストの強力な特長の一つは、ペアというLispの基本的データ構造をそのまま使っているということなので、構築はまったく難しくありません。
(define alist '((foo . 1) (bar . 2))) (cons (cons 'baz 3) alist) ; キーbaz、値3のペアを追加したalistを作成 (acons 'baz 3 alist) ; 同じことをする
連想リストのルックアップには、比較手続きの異なるバージョンごとにassq、assv、assocという3つの手続きがあります。assqはeq?、assovはeqv?、assocはequal?を使ってキーを比較します。
(assq foo alist) ; => (foo 1)
assq系の手続きが返す値は見つかったキーを含むペアで、何も見つからなかったときには#fが返されます。ペアではなく値だけを得たい場合はassq-ref、assv-ref、assoc-refを使います。
(assq-ref foo alist) ; => 1
slot-refやhash-table-getのような手続きと比べると、キーを引数の第1引数に指定するassq系の手続きは引数の順番が普通と逆になっているように思えますが、これは恐らく歴史的な事情でしょう。assq系の関数の起源は古くて、Lisp 1.5にすでに存在するのですが、そのころからこの引数順のようです。
util.listモジュールには、値でペアを探すrassq、連想リストに破壊的変更を行うassq-set!といった手続きが定義されています。連想リストに破壊的変更を行うのはあまりお勧めしませんが（破壊的変更を行うならそもそもハッシュテーブルなどを使えばよいので）、ざっとマニュアルのそのセクションを見て手続きを把握しておくとよいと思います。
参照
リファレンスマニュアル: acons、assq、assv、assoc、assq-ref、rassq、assq-set!、util.listモジュール
