#
Chapter 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. Eg,

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