1 ;; Exercise 3.25. Generalizing one- and two-dimensional tables, show how to implement a table in which values are stored under an arbitrary number of keys and different values may be stored under different numbers of keys. The lookup and insert! procedures should take as input a list of keys used to access the table.
3 ;; we could actually keep the procedure as-is, by treating the list of keys as a single key and comparing equality of lists. The downside to this is that there would be no organization based on keys.
5 (define (make-table) (list '*table*))
7 (define (assoc key records)
8 (cond ((null? records) false)
9 ((equal? key (caar records)) (car records))
10 (else (assoc key (cdr records)))))
12 (define (lookup keys table)
14 (error "no keys passed to lookup")
15 (let ((subtable (assoc (car keys) (cdr table))))
17 (if (null? (cdr keys))
19 (lookup (cdr keys) subtable))
27 (let ((local-table (list '*table*)))
28 (define (lookup key-1 key-2)
29 (let ((subtable (assoc key-1 (cdr local-table))))
31 (let ((record (assoc key-2 (cdr subtable))))
36 (define (insert! key-1 key-2 value)
37 (let ((subtable (assoc key-1 (cdr local-table))))
39 (let ((record (assoc key-2 (cdr subtable))))
41 (set-cdr! record value)
43 (cons (cons key-2 value)
51 (cond ((eq? m 'lookup-proc) lookup)
52 ((eq? m 'insert-proc!) insert!)
53 (else (error "Unknown operation -- TABLE" m))))
56 (define (test-case actual expected)
61 (display "Expected: ")
65 (define tbl (make-table))
66 ;; 2nd number refers to population in millions
67 (insert! '(usa california los-angeles) 3.88 tbl)
68 (insert! '(usa new-york new-york) 8.41 tbl)
69 (insert! '(china beijing) 21.15 tbl)
70 (insert! '(china shanghai) 24.15 tbl)
71 (insert! '(pakistan karachi) 23.5 tbl)
72 (insert! '(hong-kong) 7.22 tbl)
73 (insert! '(singapore) 5.4 tbl)
74 (test-case (lookup '(usa california los-angeles) tbl) 3.88)
75 (test-case (lookup '(china shanghai) tbl) 24.15)
76 (test-case (lookup '(singapore) tbl) 5.4)
77 (test-case (lookup '(usa california rowland-heights) tbl) #f)
78 (test-case (lookup '(usa new-york) tbl) #f)
79 (test-case (lookup '(usa new-york new-york) tbl) 8.41)
80 (test-case (lookup '(usa new-york new-york new-york) tbl) #f)