連想リストを使う


Tag: リスト

対をリストにしたものを連想リスト(association list)(alist?とも呼ばれる)と呼びます。 Lisp では簡単なテーブルが必要な場合にハッシュテーブルの代わりに、リストの要素である対の car をキーとし cdr を値とする連想リストをテーブルとして使うことがあります。要素が少ない場合にはハッシュ値の計算などのオーバーヘッドもあり、ハッシュテーブルの方が低速になることもあります。

連想リストを生成する場合には単純に quotelist を使ったり、必要に応じて バッククォート を使ったりします。

(defparameter *alist*
  '((one . 1)
    (two . 2)
    (three . 3)))

要素を追加するには cons を使います。

(cons (cons 'four 4) *alist*) 
;=> ((FOUR . 4) (ONE . 1) (TWO . 2) (THREE . 3))

便利な専用の関数として、acons があります。

(acons 'four 4 alist) 
;=> ((FOUR . 4) (ONE . 1) (TWO . 2) (THREE . 3))

連想リストの参照には assoc 関数を使います。与えられたオブジェクトとキーの一致をテストする為の関数は、:testキーワードで指定でき省略するとデフォルトの eqlが使用されます。 また、assoc-ifは、テストする関数を引数にとり結果が真となるものを返します。

(assoc 'one *alist*) 
;=> (ONE . 1)
(assoc 'five *alist* :test #'eq) 
;=> nil
(assoc-if (lambda (x) (eq x 'one)) *alist*) 
;=> (ONE . 1)

キーではなく、値の方で検索する場合には、rassocを利用します。

(rassoc 1 *alist*) 
;=> (ONE . 1)
(rassoc-if (lambda (x) (eq x 1)) *alist*) 
;=> (ONE . 1)