►zthomae’s SICP solutions
▼3 Chapter 3
3.1 Exercise 3.1
3.2 Exercise 3.2
3.3 Exercise 3.3
3.4 Exercise 3.4
3.5 Exercise 3.5
3.6 Exercise 3.6
3.7 Exercise 3.7
3.8 Exercise 3.8
3.9 Exercise 3.9
3.10 Exercise 3.10
3.11 Exercise 3.11
3.12 Exercise 3.12
3.13 Exercise 3.13
3.14 Exercise 3.14
3.15 Exercise 3.15
3.16 Exercise 3.16
3.17 Exercise 3.17
3.18 Exercise 3.18
3.19 Exercise 3.19
3.20 Exercise 3.20
3.21 Exercise 3.21
3.22 Exercise 3.22
3.23 Exercise 3.23
3.24 Exercise 3.24
3.25 Exercise 3.25
3.26 Exercise 3.26
3.27 Exercise 3.27
3.28 Exercise 3.28
3.29 Exercise 3.29
3.30 Exercise 3.30
3.31 Exercise 3.31
3.32 Exercise 3.32
3.33 Exercise 3.33
3.34 Exercise 3.34
3.35 Exercise 3.35
3.36 Exercise 3.36
3.37 Exercise 3.37
3.38 Exercise 3.38
3.39 Exercise 3.39
3.40 Exercise 3.40
3.41 Exercise 3.41
3.42 Exercise 3.42
3.43 Exercise 3.43
3.44 Exercise 3.44
3.45 Exercise 3.45
3.46 Exercise 3.46
3.47 Exercise 3.47
3.48 Exercise 3.48
3.49 Exercise 3.49
3.50 Exercise 3.50
3.51 Exercise 3.51
3.52 Exercise 3.52
3.53 Exercise 3.53
3.54 Exercise 3.54
3.55 Exercise 3.55
3.56 Exercise 3.56
3.57 Exercise 3.57
3.58 Exercise 3.58
3.59 Exercise 3.59
3.60 Exercise 3.60
3.61 Exercise 3.61
3.62 Exercise 3.62
3.63 Exercise 3.63
3.64 Exercise 3.64
3.65 Exercise 3.65
3.66 Exercise 3.66
3.67 Exercise 3.67
3.68 Exercise 3.68
3.69 Exercise 3.69
3.70 Exercise 3.70
3.71 Exercise 3.71
3.72 Exercise 3.72
3.73 Exercise 3.73
3.74 Exercise 3.74
3.75 Exercise 3.75
3.76 Exercise 3.76
3.77 Exercise 3.77
3.78 Exercise 3.78
3.79 Exercise 3.79
3.80 Exercise 3.80
3.81 Exercise 3.81
3.82 Exercise 3.82
    ← prev  up  next → 

3.26 Exercise 3.26

Suppose at first that we will only allow keys to be numbers, like in Exercise 2.66. Besides slightly changing conventions to match the ones we have now, the only new work we have to do is adding an insert! procedure to modify the binary tree.

The most significant change is that every tree root must also contain a "dummy" first entry, so that we have a pointer to a tree that we can use set-cdr! on. This is accomplished by using the make-table procedure defined earlier to create our empty trees (after all, if a tree is a table, then every subtree is also a table). Other than this change, the logic is almost identical, and the two procedures are almost identical.

(define (lookup table)
  (lambda (key)
    (let ((entries (cdr table)))
      (if (null? entries)
          false
          (let ((e (entry entries)))
            (let ((entry-key (car e))
                  (entry-val (cdr e)))
              (cond ((= key entry-key) entry-val)
                    ((< key entry-key) ((lookup (left-branch entries)) key))
                    ((> key entry-key) ((lookup (right-branch entries)) key)))))))))
(define (insert! table)
  (lambda (key value)
    (let ((entries (cdr table)))
      (if (null? entries)
          (set-cdr! table (make-tree (cons key value) (make-table) (make-table)))
          (let ((e (entry entries)))
            (let ((entry-key (car e)))
              (cond ((= key entry-key) (set-cdr! e value))
                    ((< key entry-key) ((insert! (left-branch entries)) key value))
                    ((> key entry-key) ((insert! (right-branch entries)) key value)))))))))

An example of this in use:

> (define t (make-table))
> (define lookup_t (lookup t))
> (define insert!_t (insert! t))
> (insert!_t 4 5)
> (lookup_t 4)

5

> (insert!_t 3 8)
> (insert!_t 2 1)
> (insert!_t 7 4)
> (lookup_t 3)

8

> (lookup_t 2)

1

> (lookup_t 7)

4

> (pretty-display t)

{*table*

 {4 . 5}

 {*table* {3 . 8} {*table* {2 . 1} {*table*} {*table*}} {*table*}}

 {*table* {7 . 4} {*table*} {*table*}}}

In order to store any orderable data type as a key in the table, we must also supply an ordering function to these operations. One way to do this is to make higher-order functions that return lookup and insert! functions with the ordering function bound. To make this easier to use, we can standardize our comparator function to follow this format:

cmp(a, b) = -1 if a < b

          |  0 if a = b

          |  1 if a > b

An implementation of generic tables is as follows:

(define (make-lookup cmp)
  (let ((lt (lambda (a b) (= -1 (cmp a b))))
        (eq (lambda (a b) (= 0 (cmp a b))))
        (gt (lambda (a b) (= 1 (cmp a b)))))
    (lambda (table)
      (lambda (key)
        (let ((entries (cdr table)))
          (if (null? entries)
              false
              (let ((e (entry entries)))
                (let ((entry-key (car e))
                      (entry-val (cdr e)))
                  (cond ((eq key entry-key) entry-val)
                        ((lt key entry-key) ((lookup (left-branch entries)) key))
                        ((gt key entry-key) ((lookup (right-branch entries)) key)))))))))))
(define (make-insert! cmp)
  (let ((lt (lambda (a b) (= -1 (cmp a b))))
        (eq (lambda (a b) (= 0 (cmp a b))))
        (gt (lambda (a b) (= 1 (cmp a b)))))
    (lambda (table)
      (lambda (key value)
        (let ((entries (cdr table)))
          (if (null? entries)
              (set-cdr! table (make-tree (cons key value) (make-table) (make-table)))
              (let ((e (entry entries)))
                (let ((entry-key (car e)))
                  (cond ((eq key entry-key) (set-cdr! e value))
                        ((lt key entry-key) ((insert! (left-branch entries)) key value))
                        ((gt key entry-key) ((insert! (right-branch entries)) key value)))))))))))
    ← prev  up  next →