愛すべき連想リスト

アクセスユーティリティ


alist getter-utility

連想リスト (alist)

Lispの連想リストはList構造の自然な拡張で、
keyとvalueの対を要素とするリストです。

アクセス関数は car, cdr, if, 比較関数 があれば実現でき、
データのコンストラクトも cons で可能です。

assoc の返り値は、
key-value のペアまたは見つからなかった場合 #f が返ります。
手続き自体がアクセサでもあり述語でもあるわけです。

key-valueペアに対して car, cdr でデータアクセスできますが、
毎回書くと面倒なので上記のアクセサを用意してみました。*1

欠点

  • アクセス効率が悪い
追記(2015/2/17)
メモリ効率が悪いは誤りでした。
連想リストはリスト構造であるため、
一般的に、メモリ使用効率はハッシュテーブルより優れています。

SRFI-69 で Hash-Table も規定されており、
多くのScheme処理系で Hash-Table や
同等のアクセス効率の良いデータ構造がサポートされているので、
実用において、alistを利用する可能性は少ない思われます。

追記(2015/2/17)
実際alistの利用状況はどうなのかと思いgithubでSerchをかけてみました。
ヒット数を見る限り、連想リストは広く利用されているようです。

Search · assq · GitHub
Search · assv · GitHub
Search · hash-table-ref · GitHub

それでも連想リストは複雑なデータ構造の用意なく利用できるため、
Lisp方言を作り始める初期の頃にお世話になると思います。

おわりに

連想リストは実用で利用するケースの少ない構造ですが、
Lispの入門書などでも、ほぼ必ず取り上げられる機能です。

素敵なデータ構造なので、
ぜひ一度利用してみてください。

*1:getterが#fを返してしまうと,呼び出し側がデータが判別できないという欠点付きです