Chapter 10

A-リストとテーブル

連想リストあるいはA-リストは、特別なフォーマットの Scheme のリストです。リストの各要素はコンスセルで、car 部はキー、 cdr 部はそのキーに結びついた値です。例は以下の通り。

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

手続き呼び出し (assv k al) は A-リスト al 中で、 キー k に結びついているコンスセルを探します。A-リスト 中のキーは、同値性述語 eqv? をつかって、与えれられた k と比較されます。一般には、キー比較に別の述語が欲しくなるかもしれません。 たとえば、キーが大文字小文字を区別しない文字列であった場合には eqv? ではあまり役に立ちません。

ここで、テーブル(table)と呼ばれる構造体を定義しましょう。 これは、キーに関して、ユーザ定義の述語を使えるようにしたものです。 フィールドは equ と alist です。

(defstruct table (equ eqv?) (alist '()))

(デフォルトの述語は eqv? — 通常のA-リストと同じ — で、 alist は最初は空です。)

あたえられたキーに結びついた(コンスセルではなく)値を得るのに table-get という手続きを使うことにしましょう。 table-get はテーブルとキーを引数とし、キーが指定した テーブル中になかった場合に返すデフォルト値をオプション引数とします。

(define table-get
  (lambda (tbl k . d)
    (let ((c (lassoc k (table.alist tbl) (table.equ tbl))))
      (cond (c (cdr c))
            ((pair? d) (car d))))))

table-get 中で使う、手続き lassoc は以下のように定義します。

(define lassoc
  (lambda (k al equ?)
    (let loop ((al al))
      (if (null? al) #f
          (let ((c (car al)))
            (if (equ? (car c) k) c
                (loop (cdr al))))))))

あたえられたテーブルのキーの値を更新するのには table-put! を使います。

(define table-put!
  (lambda (tbl k v)
    (let ((al (table.alist tbl)))
      (let ((c (lassoc k al (table.equ tbl))))
        (if c (set-cdr! c v)
            (set!table.alist tbl (cons (cons k v) al)))))))

手続き table-for-each は与えられた手続きをテーブル中の すべてのキー/値の対について呼びだします。

(define table-for-each
  (lambda (tbl p)
    (for-each
     (lambda (c)
       (p (car c) (cdr c)))
     (table.alist tbl))))