10  Alists and tables

An association list, or alist, is a Scheme list of a special format. Each element of the list is a cons cell, the car of which is called a key, the cdr being the value associated with the key. E.g.,

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

The procedure call (assv k al) finds the cons cell associated with key k in alist al. The keys of the alist are compared against the given k using the equality predicate eqv?. In general, though we may want a different predicate for key comparison. For instance, if the keys were case-insensitive strings, the predicate eqv? is not very useful.

We now define a structure called table, which is a souped-up alist that allows user-defined predicates on its keys. Its fields are equ and alist.

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

(The default predicate is eqv? — as for an ordinary alist — and the alist is initially empty.)

We will use the procedure table‑get to get the value (as opposed to the cons cell) associated with a given key. table‑get takes a table and key arguments, followed by an optional default value that is returned if the key was not found in the table:

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

The procedure lassoc, used in table‑get, is defined as:

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

The procedure table‑put! is used to update a key’s value in the given table:

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

The procedure table‑for‑each calls the given procedure on every key/value pair in the table

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