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 &optional testfn

この関数はalist要素にたいしてtestfnが関数ならtestfn、それ以外ならequalを使用して、alist内からkeyをもつ最初の連想をリターンする。testfnが関数の場合にはalistの要素のCAR、keyとおう2つの引数で呼び出される。testfnでテストした結果、CARがkeyと一致する連想が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を比較する。この関数は与えられた値に対応するキーを探す、assocの逆バージョンと考えることができよう。

Function: assq key alist

この関数はalistからkeyをもつ最初の連想値をリターンする点はassocと同様だが、比較に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か("simple leaves" . oak)かもしれない
(assoc "simple leaves" leaves)
     ⇒ ("simple leaves" . oak)

Function: alist-get key alist &optional default remove testfn

この関数はassqと似ている。これはalistの要素のkeyを比較して最初の連想(key . value)を見つける。連想が見つからなければ、関数はdefaultをリターンする。alistにたいするkeyの比較にはtestfnで指定された関数を使用する(デフォルトはeq)。

これはsetfでの値の変更に使用できる汎変数(Generalized Variablesを参照)。値の値へのセットにこれを使用する際にオプション引数removeがnilの場合は、新たな値がdefaultとeqlならalistからkeyの連想を削除することを意味する。

Function: rassq value alist

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

rassqはassqと似ていますが、CARではなくalistの各連想のCDRを比較します。この関数を、与えられた値に対応するキーを探す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 (list '(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: assoc-delete-all key alist &optional test

この関数はassq-delete-allと同様だが、オプション引数test ( alist内のキーを比較するための述語関数)を受け取る点が異なる。testが省略かnilならデフォルトはequal。この関数はassq-delete-allのように、多くの場合はalistの元のリスト構造を変更する。

Function: rassq-delete-all value alist

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

Macro: let-alist alist body

連想リストalistのキーとして使用される先頭にドットを付したシンボルそれぞれにたいしてバインディングを作成する。これは同じ連想リスト内の複数のアイテムにアクセスする際に有用かもしれない。理解するためにもっともよいのは以下のシンプルな例だろう:

(setq colors '((rose . red) (lily . white) (buttercup . yellow)))
(let-alist colors
  (if (eq .rose 'red)
      .lily))
     ⇒ white

bodyをコンパイル時に検査して、body内に出現する先頭文字として‘.’を付したシンボルだけがバインドされる。キーの検索はassq、このassqのリターン値のcdrがそのバインディングにたいする値として割り当てられる。

ネストされた連想リストをサポートする:

(setq colors '((rose . red) (lily (belladonna . yellow) (brindisi . pink))))
(let-alist colors
  (if (eq .rose 'red)
      .lily.belladonna))
     ⇒ yellow

互いに内部にlet-alistをネストすることが可能だが、内側のlet-alistは外側のlet-alistがバインドする変数にはアクセスできない。