Prev Up Next

## 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))))
```