Representing Tables
Intro
We have mentioned in Unit 2 that we can store data using a 2 dimensional table and, given 2 keys, can fetch the desired data. We can use mutable lists to represent this data structure by first building a 1 dimensional table and extending the idea.
Before We Start: assoc
Before we dive in to tables, we have to explore another Scheme compound procedure, assoc, which will play a huge role. assoc accepts a key and a list of pairs, and returns the first pair that has key as its car. If no such pairs exist, it returns #f. Look at the series of examples below to understand what assoc does.
> (assoc 1 '((1 2) (3 4)))
(1 2) ;returns the pair with car 1
> (assoc 'cupcake '((1 2) (3 4) (cupcake donut) (galaxy star)))
(cupcake donut) ;anything can be a key.
> (assoc 2 '((1 2) (3 4)))
#f ;No pair has 2 as its car, hence returns #f
> (assoc 'froyo '((cupcake donut eclair)
(froyo gingerbread honeycomb)
(sandwich jellybean kitkat)))
(froyo gingerbread honeycomb) ;Pairs can be of any length
Here is the formal definition for assoc:
(define (assoc key records)
(cond ((null? records) false)
((equal? key (caar records)) (car records))
(else (assoc key (cdr records)))))
1-Dimensional Tables
In a 1D table, values are stored under a single key. A table will be designed
as a list of pairs. Each pairs' car hold the key for each value.
In the above table, the breakdown between the keys and values can be seen below.
| Keys | Values |
|---|---|
a |
1 |
b |
2 |
c |
3 |
Why does our table point to a pair that doesn't contain any key-value pair? We
designed our table so that the first pair holds the symbol *table* which
signifies that the current list structure we're looking at is a table.
make-table
Here is the simple constructor for our table:
(define (make-table)
(list '*table*))
lookup
To extract information from a table, we use the lookup selector, which takes
a key as argument and returns the associated value (or #f if there is no
value stored under that key). Here's our definition of lookup
(define (lookup key table)
(let ((record (assoc key (cdr table))))
(if record
(cdr record)
false)))
> (lookup 'b table) ;table refers to the table made above
2
insert!
To insert a key-value pair in a table, we follow this simple algorithm:
- If key is already in the list, just update the value
Otherwise, make a new key-value pair and attach it to the table
(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)
2-Dimensional Tables
In a 2D table, each value is specified by two keys. We can construct such a table as a 1 dimensional table in which each key identifies a subtable. Say we have 2 tables: "math" and "letters" with the following key-value pairs.
math:
+ : 43
- : 45
* : 42
letters:
a : 97
b : 98
We can put them into one big table:
lookup
To find a value in a 2D table, you will need 2 keys. The first key is used to find the correct subtable. The second key is used to find the correct value in that subtable.
(define (lookup key-1 key-2 table)
(let ((subtable (assoc key-1 (cdr table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(cdr record)
#f))
#f)))
insert
To insert into a 2D table, you also need 2 keys. The first key is used to try
and find the correct subtable. If a subtable with the first key doesn't exist,
make a new subtable. If the table exists, use the exact same algorithm we have
for the 1 dimensional insert!.
(define (insert! key-1 key-2 value table)
(let ((subtable (assoc key-1 (cdr table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(set-cdr! record value)
(set-cdr! subtable
(cons (cons key-2 value)
(cdr subtable)))))
(set-cdr! table
(cons (list key-1
(cons key-2 value))
(cdr table)))))
'ok)
Local Tables
The lookup andinsert! operations defined above take the table as an argument. This enables us to use programs that access more than one table. Another way to deal with multiple tables is to have separate lookup and insert! procedures for each table. We can do this by representing a table procedurally, as an object that maintains an internal table as part of its local state. When sent an appropriate message, this "table object'' supplies the procedure with which to operate on the internal table. Here is a generator for two-dimensional tables represented in this fashion:
(define (make-table)
(let ((local-table (list '*table*)))
(define (lookup key-1 key-2)
(let ((subtable (assoc key-1 (cdr local-table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(cdr record)
false))
false)))
(define (insert! key-1 key-2 value)
(let ((subtable (assoc key-1 (cdr local-table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(set-cdr! record value)
(set-cdr! subtable
(cons (cons key-2 value)
(cdr subtable)))))
(set-cdr! local-table
(cons (list key-1
(cons key-2 value))
(cdr local-table)))))
'ok)
(define (dispatch m)
(cond ((eq? m 'lookup-proc) lookup)
((eq? m 'insert-proc!) insert!)
(else (error "Unknown operation -- TABLE" m))))
dispatch))
get and put
In Unit 2's "Data Directed" subsection, we used a 2D table to store a value
under 2 keys using the procedures get and put.
(put <key-1> <key-2> <value>)
(get <key-1> <key-2>)
We can now define these procedures using our tables!
(define operation-table (make-table))
(define get (operation-table 'lookup-proc))
(define put (operation-table 'insert-proc!))
get takes as arguments two keys, and put takes as arguments two keys and a value. Both operations access the same local table, which is encapsulated within the object created by the call to make-table.