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))))
Prev Up Next