第十章 关联表和表格

关联表是Scheme一种特殊形式的列表。列表的每一个元素都是一个点对，其中的car（左边的元素）被称为一个“键”，cdr（右边的元素）被称为和该键关联的值。例如：

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

调用程序(assv k al)能在关联表al中找到和键k关联的CONS单元。在查找时关联表中的键与k使用eqv?过程来比较。然而有时我们可能希望自定义一个键的比较函数。例如，如果键是不区分大小写的字符串，那默认的eqv?就没什么用了。

我们现在定义一个结构table(表格)，这是一个改进后的关联表，它可以允许用户在它的键上自定义比较函数。它的字段是equ和alist。

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

（默认的比较函数是eqv?——对于一个普通的关联表——关联表的初始化为空。）

我们将使用程序table-get得到与一个给定键关联的值（相对于cons单元）。table-get接受一个table(表格)和一个键作为参数，还有一个可选的默认值，这样若在表格中未找到该键则返回该默认值：

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

在table-get中使用的程序lassoc，定义如下：

  1. (define lassoc
  2.   (lambda (k al equ?)
  3.     (let loop ((al al))
  4.       (if (null? al) #f
  5.           (let ((c (car al)))
  6.             (if (equ? (car c) k) c
  7.                 (loop (cdr al))))))))

程序table-put用来更新给定表格中的一个键的值：

  1. (define table-put!
  2.   (lambda (tbl k v)
  3.     (let ((al (table.alist tbl)))
  4.       (let ((c (lassoc k al (table.equ tbl))))
  5.         (if c (set-cdr! c v)
  6.             (set!table.alist tbl (cons (cons k v) al)))))))

程序table-for-each为每个表格中键/值对调用给定的程序

  1. (define table-for-each
  2.   (lambda (tbl p)
  3.     (for-each
  4.      (lambda (c)
  5.        (p (car c) (cdr c)))
  6.      (table.alist tbl))))