►zthomae’s SICP solutions
▼2 Chapter 2
2.1 Exercise 2.1
2.2 Exercise 2.2
2.3 Exercise 2.3
2.4 Exercise 2.4
2.5 Exercise 2.5
2.6 Exercise 2.6
2.7 Exercise 2.7
2.8 Exercise 2.8
2.9 Exercise 2.9
2.10 Exercise 2.10
2.11 Exercise 2.11
2.12 Exercise 2.12
2.13 Exercise 2.13
2.14 Exercise 2.14
2.15 Exercise 2.15
2.16 Exercise 2.16
2.17 Exercise 2.17
2.18 Exercise 2.18
2.19 Exercise 2.19
2.20 Exercise 2.20
2.21 Exercise 2.21
2.22 Exercise 2.22
2.23 Exercise 2.23
2.24 Exercise 2.24
2.25 Exercise 2.25
2.26 Exercise 2.26
2.27 Exercise 2.27
2.28 Exercise 2.28
2.29 Exercise 2.29
2.30 Exercise 2.30
2.31 Exercise 2.31
2.32 Exercise 2.32
2.33 Exercise 2.33
2.34 Exercise 2.34
2.35 Exercise 2.35
2.36 Exercise 2.36
2.37 Exercise 2.37
2.38 Exercise 2.38
2.39 Exercise 2.39
2.40 Exercise 2.40
2.41 Exercise 2.41
2.42 Exercise 2.42
2.43 Exercise 2.43
2.44 Exercise 2.44
2.45 Exercise 2.45
2.46 Exercise 2.46
2.47 Exercise 2.47
2.48 Exercise 2.48
2.49 Exercise 2.49
2.50 Exercise 2.50
2.51 Exercise 2.51
2.52 Exercise 2.52
2.53 Exercise 2.53
2.54 Exercise 2.54
2.55 Exercise 2.55
2.56 Exercise 2.56
2.57 Exercise 2.57
2.58 Exercise 2.58
2.59 Exercise 2.59
2.60 Exercise 2.60
2.61 Exercise 2.61
2.62 Exercise 2.62
2.63 Exercise 2.63
2.64 Exercise 2.64
2.65 Exercise 2.65
2.66 Exercise 2.66
2.67 Exercise 2.67
2.68 Exercise 2.68
2.69 Exercise 2.69
2.70 Exercise 2.70
2.71 Exercise 2.71
2.72 Exercise 2.72
2.73 Exercise 2.73
2.74 Exercise 2.74
2.75 Exercise 2.75
2.76 Exercise 2.76
2.77 Exercise 2.77
2.78 Exercise 2.78
2.79 Exercise 2.79
2.80 Exercise 2.80
2.81 Exercise 2.81
2.82 Exercise 2.82
2.83 Exercise 2.83
2.84 Exercise 2.84
2.85 Exercise 2.85
2.86 Exercise 2.86
2.87 Exercise 2.87
2.88 Exercise 2.88
2.89 Exercise 2.89
2.90 Exercise 2.90
2.91 Exercise 2.91
2.92 Exercise 2.92
2.93 Exercise 2.93
2.94 Exercise 2.94
2.95 Exercise 2.95
2.96 Exercise 2.96
2.97 Exercise 2.97
    ← prev  up  next → 

2.68 Exercise 2.68

encode-symbol requires us to visit all of the nodes in the tree, and must return a list of bits representing the path to the node containing the symbol we are looking for if it is present in the tree. The exercise asks us to throw an error if the symbol is not found. We will handle this (and only this) in an outer procedure, while doing the traversal and message returning inside an inner procedure, because it is rather elegant to return nil if the symbol is not found.

First, the inner procedure, named encode-symbol-1:

(define (encode-symbol-1 symbol tree bits)
  (if (leaf? tree)
      (if (eq? symbol (symbol-leaf tree))
          bits
          '())
      (append
       (encode-symbol-1 symbol (left-branch tree) (append bits '(0)))
       (encode-symbol-1 symbol (right-branch tree) (append bits '(1))))))

When encode-symbol-1 is visiting a current node (the root of tree), bits contains the encoded path to this node. Therefore, if the current node is a leaf and its symbol is the one we’re looking for, we can return bits. If the current node is a leaf and the symbol is not the one we’re looking for, there’s no more work to be done in the tree and we return nil, for reasons that will become clearer soon.

If the current node is not a leaf, we need to search both the left and right subtrees for the symbol. We can call encode-symbol-1 with the left and right branches of the tree and with 0 and 1 appended to bits, respectively. This encodes the path we have taken through the tree into the list of bits.

However, despite doing two recursive searches for the symbol, we only want to return one list of bits. The easiest way to do this is to append the results together, and to make sure that we return nil if we don’t find the symbol. This will make the final result be the same as the bit encoding of the symbol in the tree.

To return an error when the symbol isn’t found, we can write a simple wrapper procedure as our actual encode-symbol:

(define (encode-symbol symbol tree)
  (let ((result (encode-symbol-1 symbol tree '())))
    (if (null? result)
        (error "Couldn't find symbol in tree")
        result)))

To verify that this works, we can add to our equal? procedure from Exercise 2.54 to also check equality of numbers, and then use if to verify that the sample encoded message is the same as a message we encode ourselves using our previously decoded message:

(define (equal? a b)
  (cond
    ((and (null? a) (null? b)) #t)
    ((and (symbol? a) (symbol? b))
     (eq? a b))
    ((and (number? a) (number? b))
     (= a b))
    ((and (list? a) (list? b))
     (if (or (null? a) (null? b)) #f
         (and
          (equal? (car a) (car b))
          (equal? (cdr a) (cdr b)))))
    (else #f)))
> (define (encode message tree)
    (if (null? message)
        nil
        (append (encode-symbol (car message) tree)
                (encode (cdr message) tree))))
> (equal? sample-message (encode (decode sample-message sample-tree) sample-tree))

#t

    ← prev  up  next →