連想リストを使う


Tags: リスト, R6RS, SRFI

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

連想リストを生成する場合には単純に quotelist を使ったり、必要に応じて quasiquote を使ったりする。

(import (rnrs))

(define alist
  '((one . 1)
    (two . 2)
    (three . 3)))

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

(cons (cons 'four 4) alist) ; => ((four . 4) (one . 1) (two . 2) (three . 3))

便利な略記法として SRFI-1 には alist-cons という手続きがある。

(import (rnrs) (only (srfi :1) alist-cons))

(alist-cons 'four 4 alist) ; => ((four . 4) (one . 1) (two . 2) (three . 3))

連想リストの参照には assoc, assv, assq, assp といった手続きを使う。それぞれ引数として与えられたオブジェクトとキーが equal?, eqv?, eq? な連想リスト中の対、与えられた述語をキーが満たす対を返す。

(assoc 'one alist) => (one . 1)
(assq 'five alist) ; => #f
(assp (lambda (x) (eq? x 'one)) alist) ; => (one . 1)

値だけを取り出したい場合にはイディオムとして cond や SRFI-2 の and-let* を使う。

(import (rnrs) (srfi :2))

(cond ((assq 'one alist) => cdr)
      (else #f)) ; => 1

(cond ((assq 'six alist) => cdr)
      (else #f)) ; => #f

(and-let* ((p (assq 'three alist)))
  (cdr p)) ; => 3