A table mutates records while lookup keeps the representation private.
An association list can live behind lookup and insert! so an existing record changes in place, a missing record is linked into the table, and a second key introduces a nested subtable without changing the client protocol.
Which links must change when a table updates one record or creates a new nested key path?
- Use assoc to locate a mutable record behind a table header
- Update an existing record with set-cdr!
- Insert a new record by changing the table tail
- Represent a two-key table as subtables containing records
- Distinguish lookup failure from a stored value
The one-key table is a mutable list whose first element is a private header. lookup searches only the records after that header. insert! mutates the cdr of an existing key-value pair when the key is present; otherwise it changes the table header pair so a new record becomes part of the association list. Client code does not depend on insertion order or pair layout.
The two-key table stores a first-key record whose cdr is itself an association list. Inserting a new second key mutates that subtable, while a new first key links an entire subtable into the outer table. Updating arithmetic from 10 to 11 changes the existing innermost record rather than creating a duplicate. These examples use #f as the missing result, so storing #f would require a richer lookup protocol.
(begin
(define (make-table) (list '*table*))
(define (lookup key table)
(let ((record (assoc key (cdr table))))
(if record (cdr record) #f)))
(define (insert! key value table)
(let ((record (assoc key (cdr table))))
(if record
(set-cdr! record value)
(set-cdr! table
(cons (cons key value)
(cdr table)))))
'ok)
(define table (make-table))
(insert! 'alpha 4 table)
(insert! 'beta 5 table)
(insert! 'alpha 9 table)
(list (lookup 'alpha table)
(lookup 'beta table)
(lookup 'gamma table)
table))- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns (9 5 #f (*table* (beta . 5) (alpha . 9))). The second returns (11 20 30 #f (*table* (language (scheme . 30)) (math (algebra . 20) (arithmetic . 11)))).
Compare assoc traversals that find alpha with the gamma traversal that reaches the end. Distinguish set-cdr! on an existing record from set-cdr! on the table or subtable header that links a new record. In the nested run, follow the outer key before the inner key and verify that the arithmetic update changes one existing pair.
Change the program before you read the hint.
Add physics under math, update scheme to 31, and add a second language record. Predict the outer and inner record order before running, then explain which updates mutate records and which mutate table tails.
Show one hint
A present key changes the cdr of its record. A missing key creates a new pair and links it at the front of the relevant association list.