5.8 連想リスト

連想配列(association list、短くはalist)は、キーと値のマッピングを記録します。これは連想(associations)と呼ばれるコンスセルのリストです。各コンスセルにおいてCARはキー(key)で、CDRは連想値(associated value)となります。³

以下はalistの例です。キーpineは値cones、キーoakはacorns、キーmapleはseedsに関連付けられます。

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

alist内の値とキーには、任意のLispオブジェクトを指定できます。たとえば以下のalist0では、シンボルaは数字1、文字列"b"はリスト(2 3)(alist要素のCDR)に関連付けられます。

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

要素のCDRのCARに連想値を格納するようにalistデザインするほうがよい場合があります。以下はそのようなalistです。

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

この例では、redがroseに関連付けられる値だと考えます。この種のalistの利点は、CDRのCDRの中に他の関連する情報 — 他のアイテムのリストでさえも — を格納することができることです。不利な点は、与えられた値を含む要素を見つけるためにrassq(以下参照)を使用できないことです。これらを検討することが重要でない場合には、すべての与えられたalistにたいして一貫している限り、選択は好みの問題といえます。

上記で示したのと同じalistは、要素のCDRに連想値をもつと考えることができます。この場合、roseに関連付けられる値はリスト(red)になるでしょう。

連想リストは新しい連想値を簡単にリストの先頭に追加できるので、スタックに保持したいような情報を記録するのによく使用されます。連想リストから与えられたキーにたいして連想値を検索する場合、それが複数ある場合は、最初に見つかったものがreturnされます。

Emacs Lispでは、連想リストがコンスセルでなくても、それはエラーではありません。alist検索関数は、単にそのような要素を無視します。多くの他のバージョンのLispでは、このような場合はエラーをシグナルします。

いくつかの観点において、プロパティーリストは連想リストと似ていることに注意してください。それぞれのキーが一度だけ出現するような場合、プロパティーリストは連想リストと同様に振る舞います。プロパティーリストと連想リストの比較については、Property Listsを参照してください。

Function: assoc key alist

この関数は、alist要素にたいしてkeyを比較するのにequalを使用して、alist内からkeyをもつ最初の連想をリターンする。CARがkeyとequalであるような連想値がalistになければ、この関数は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-stringはassocと似ていますが、文字列間の特定の違いを無視する点が異なります。Text Comparisonを参照してください。

Function: rassoc value alist

この関数はalistの中から値valueをもつ最初の連想をリターンする。CDRがvalueとequalであるような連想値がalistになければ、この関数はnilをリターンする。

rassocはassocと似ていますが、CARではなく、alistの連想のCDRを比較します。この関数を、与えられた値に対応するキーを探す、“reverse assoc”と考えることができます。

Function: assq key alist

この関数は、alistからkeyをもつ最初の連想値をリターンする点はassocと同様だが、比較にequalではなくeqを使用する点が異なる。CARがkeyとeqであるような連想値がalist内に存在しなければ、assqはnilをリターンする。eqはequalより早く、ほとんどのalistはキーにシンボルを使用するので、この関数はassocより多用される。Equality Predicatesを参照のこと。

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

逆にキーがシンボルではないalistでは、通常はassqは有用ではない:

(setq leaves
      '(("simple leaves" . oak)
        ("compound leaves" . horsechestnut)))

(assq "simple leaves" leaves)
     ⇒ nil
(assoc "simple leaves" leaves)
     ⇒ ("simple leaves" . oak)

Function: rassq value alist

この関数は、alist内から値valueをもつ最初の連想値をリターンする。alist内にCDRがvalueとeqであるような連想値が存在しないならnilをリターンする。

rassqはassqと似ていますが、CARではなく、alistの各連想のCDRを比較します。この関数を、与えられた値に対応するキーを探す、“reverse assq”と考えることができます。

たとえば:

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

(rassq 'acorns trees)
     ⇒ (oak . acorns)
(rassq 'spores trees)
     ⇒ nil

rassqは要素のCDRのCARに保管された値の検索はできません:

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

(rassq 'white colors)
     ⇒ nil

この場合、連想(lily white)のCDRはwhiteではなくリスト(white)です。これは連想をドットペア表記で記述すると明確になります:

(lily white) ≡ (lily . (white))

Function: assoc-default key alist &optional test default

この関数は、keyにたいするマッチをalistから検索する。alistの各要素にたいして、この関数はkeyと要素(アトムの場合)、または要素のCAR(コンスの場合)を比較する。比較はtestに2つの引数 — 要素(か要素のCAR)とkey — を与えて呼び出すことにより行なわれる。引数はこの順番で渡されるので、正規表現(Regexp Searchを参照)を含むalistでは、string-matchを使用することにより有益な結果を得ることができる。testが省略またはnilなら比較にequalが使用される。

alistの要素がこの条件によりkeyとマッチすると、assoc-defaultはその要素の値をリターンする。要素がコンスなら値は要素のCDR、それ以外ならリターン値はdefaultとなる。

keyにマッチする要素がalistに存在しないければ、assoc-defaultはnilをリターンする。

Function: copy-alist alist

この関数は深さのレベルが2のalistのコピーをリターンする。この関数は各連想の新しいコピーを作成するので、元のalistを変更せずに新しいalistを変更できる。

(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")

Function: assq-delete-all key alist

この関数は、delqを使用してマッチする要素を1つずつ削除するときのように、CARがkeyとeqであるようなすべての要素をalistから削除する。この関数は短くなったalistをリターンし、alistの元のリスト構造を変更することもよくある。正しい結果を得るために、alistに保存された値ではなくassq-delete-allのリターン値を使用すること。

(setq alist '((foo 1) (bar 2) (foo 3) (lose 4)))
     ⇒ ((foo 1) (bar 2) (foo 3) (lose 4))
(assq-delete-all 'foo alist)
     ⇒ ((bar 2) (lose 4))
alist
     ⇒ ((foo 1) (bar 2) (lose 4))

Function: rassq-delete-all value alist

この関数は、alistからCDRがvalueとeqであるようなすべての要素を削除する。この関数は短くなったリストをリターンし、alistの元のリスト構造を変更することもよくある。rassq-delete-allはassq-delete-allと似ているが、CARではなくalistの各連想のCDRを比較する。