Teach Yourself Scheme in Fixnum Days introduction to the programming language Scheme">

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) 
     (lambda (c) 
       (p (car c) (cdr c))) 
     (table.alist tbl))))