前: Sets And Lists, 上: Lists


5.8 連想リスト

連想リスト(association list)、略してalistは、 キーから値への対応付けを記録しています。 これは連想(associations)と呼ばれるコンスセルのリストです。 各コンスセルのcarkeyであり、 cdr連想値(associated value)です。 1

連想リストの例を示します。 キーpineを値conesに、キーoakを値acornsに、 キーmapleを値seedsに対応付けています。

     '((pine . cones)
       (oak . acorns)
       (maple . seeds))

連想リスト内の連想値は任意のLispオブジェクトでよく、キーもそうです。 たとえば、つぎの連想リストでは、シンボルaに数1を、 文字列"b"リスト(2 3)を対応付けています。 リスト(2 3)は連想リストの要素のcdrです。

     ((a . 1) ("b" 2 3))

要素のcdrcarに連想値を格納するように 連想リストを設計したほうがよい場合もあります。 つぎのようにします。

     '((rose red) (lily white) (buttercup yellow))

ここで、redroseに対応付けた値と考えます。 この種の連想リストの利点の1つは、関連する別の情報を、 他の項目から成るリストでさえも、cdrcdrに格納できることです。 1つの欠点は、rassq(下記参照)を使って 指定した値を含む要素を探せないことです。 これらの条件が重要でない場合には、1つの連想リストに関する限り、 一貫性があればどちらを選ぶかは好みの問題です。

上に示した連想リストは、要素のcdrに連想値が収めてあると 考えることもできます。 roseの連想値はリスト(red)になります。

連想リストはスタックなどに置くような情報の記録に使います。 というには、リストの先頭に新たな連想を追加するのが簡単だからです。 指定したキーに対する連想を連想リストから探すとき、 それらが複数個存在する場合には、最初にみつかったものを返します。

Emacs Listでは、連想リストの要素がコンスセルでなくても エラーではありません。 連想リスト探索関数はそのような要素を単に無視します。 他の多くのLispでは、そのような場面ではエラーを通知します。

属性リストもいろいろな意味で連想リストに類似しています。 属性リストは、キーが一度しか現れない連想リストのようにふるまいます。 属性リストと連想リストの比較については、See Property Lists

— 機能: assoc key alist

この関数は、alist内のkeyに対する最初の連想を返す。 keyと連想リストの各要素との比較には、 equal(see Equality Predicates)を用いる。 alistの中にcarkeyequalである連想が 存在しなければ、nilを返す。 たとえば、つぎのとおり。

          (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
               => ((pine . cones) (oak . acorns) (maple . seeds))
          (assoc 'oak trees)
               => (oak . acorns)
          (cdr (assoc 'oak trees))
               => acorns
          (assoc 'birch trees)
               => nil
     

つぎは、キーと値がシンボルではない例。

          (setq needles-per-cluster
                '((2 "Austrian Pine" "Red Pine")
                  (3 "Pitch Pine")
                  (5 "White Pine")))
          
          (cdr (assoc 3 needles-per-cluster))
               => ("Pitch Pine")
          (cdr (assoc 2 needles-per-cluster))
               => ("Austrian Pine" "Red Pine")
     

関数assoc-ignore-representationassoc-ignore-caseassocに似ていますが、 それらは比較にcompare-stringsを使う点が異なります。 See Text Comparison

— 機能: rassoc value alist

この関数は、alistの中でvalueを値とする最初の連想を返す。 alistの中にcdrvalueequalである連想が 存在しなければ、nilを返す。

rassocassocに似ているが、 alistの各連想のcarのかわりにcdrを比較する点が異なる。 指定した値に対するキーを探す『assocの逆演算』と考えることができる。

— 機能: assq key alist

この関数は、alist内のkeyに対する最初の連想を返すという意味で assocに似ているが、equalのかわりにeqで比較する。 alist内の連想のcarkeyeqであるものが存在しないと、 assqnilを返す。 この関数はassocより多用される。 というのは、eqequalより高速であり、 ほとんどの連想リストではキーとしてシンボルを使うからである。

          (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
               => ((pine . cones) (oak . acorns) (maple . seeds))
          (assq 'pine trees)
               => (pine . cones)
     

一方で、キーがシンボルではない連想リストでは、 assqは、通常、有用ではない。

          (setq leaves
                '(("simple leaves" . oak)
                  ("compound leaves" . horsechestnut)))
          
          (assq "simple leaves" leaves)
               => nil
          (assoc "simple leaves" leaves)
               => ("simple leaves" . oak)
     
— 機能: rassq value alist

この関数は、alistの中でvalueを値とする最初の連想を返す。 alistの中にcdrvalueeqである連想が 存在しなければ、nilを返す。

rassqassqに似ているが、 alistの各連想のcarのかわりにcdrを比較する点が異なる。 指定した値に対するキーを探す『assqの逆演算』と考えることができる。

たとえばつぎのとおり。

          (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
          
          (rassq 'acorns trees)
               => (oak . acorns)
          (rassq 'spores trees)
               => nil
     

rassqでは、 要素のcdrcarに格納された値を探せないことに注意。

          (setq colors '((rose red) (lily white) (buttercup yellow)))
          
          (rassq 'white colors)
               => nil
     

この場合、連想(lily white)cdrは、 シンボルwhiteではなくリスト(white)である。 連想をドット対記法で書くとこれが明確になる。

          (lily white) == (lily . (white))
     

— 機能: assoc-default key alist test default

この関数は、keyに一致するものをalistから探す。 alistの各要素について、(アトムならば)要素とkeyを、 あるいは、(コンスならば)要素のcarkeyを比較する。 比較にはこれらを2つの引数としてtestを呼び出す。 引数を渡す順序はこの順なので、 正規表現(see Regexp Search)を収めた連想リストに対して string-matchを使うと有益な結果を得られる。 testを省略したりnilであると、比較にはequalを用いる。

上の条件で連想リストの要素がkeyに一致するならば、 assoc-defaultはその要素に基づく値を返す。 要素がコンスならば値は要素のcdr。 さもなければ、戻り値はdefault

keyに一致する連想リストの要素が存在しなければ、 assoc-defaultnilを返す。

— 機能: copy-alist alist

この関数は、alistを2レベルの深さまでコピーしたものを返す。 各連想ごとに新たなコピーを作るので、 新たな連想リストの連想を変更しても、もとの連想リストは変更しない。

          (setq needles-per-cluster
                '((2 . ("Austrian Pine" "Red Pine"))
                  (3 . ("Pitch Pine"))
                  (5 . ("White Pine"))))
          =>
          ((2 "Austrian Pine" "Red Pine")
           (3 "Pitch Pine")
           (5 "White Pine"))
          
          (setq copy (copy-alist needles-per-cluster))
          =>
          ((2 "Austrian Pine" "Red Pine")
           (3 "Pitch Pine")
           (5 "White Pine"))
          
          (eq needles-per-cluster copy)
               => nil
          (equal needles-per-cluster copy)
               => t
          (eq (car needles-per-cluster) (car copy))
               => nil
          (cdr (car (cdr needles-per-cluster)))
               => ("Pitch Pine")
          (eq (cdr (car (cdr needles-per-cluster)))
              (cdr (car (cdr copy))))
               => t
     

この例は、copy-alistにより、 コピーの連想を変更して他のものになぜ影響しないかを示す。

          (setcdr (assq 3 copy) '("Martian Vacuum Pine"))
          (cdr (assq 3 needles-per-cluster))
               => ("Pitch Pine")
     

脚注

[1] この『キー』の使い方は、『キー列』とは無関係。 キーとは、表の項目を探すために使う値を意味する。 ここでは、表は連想リストであり、項目は連想リストの連想値である。