SICP Exercise 2.68: Encoding Symbols

The encode procedure takes as arguments a message and a tree and produces the list of bits that gives the encoded message.

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))

Encode-symbol is a procedure, which you must write, that returns the list of bits that encodes a given symbol according to a given tree. You should design encode-symbol so that it signals an error if the symbol is not in the tree at all. Test your procedure by encoding the result you obtained in exercise 2.67 with the sample tree and seeing whether it is the same as the original sample message.

First things first, let's deal with the error case. We're given a procedure, symbols, that will give us a list of all the symbols in a particular node of the tree. We can use this to test whether a particular node contains a symbol or not by using it in conjunction with memq which was introduced way back in section 2.3.1. memq will return false if the symbol isn't in the list, and a non-empty list otherwise, so we can use this as a predicate (since non-false values are treated as true).

With the error case out of the way, let's consider how we can generate our list of bits. We have a binary tree, so we can recurse down this to find the leaf node corresponding to the symbol we're trying to encode. We know (from the error case) that we can test whether or not our symbol is under the left or right child nodes via symbols and memq, and we know that we want to put a 0 onto the list for each time we move to a left child and a 1 onto the list for each time we move to a right child. So all we need to do is determine which branch to take at each (non-leaf) node and then cons the appropriate binary digit onto the list returned by recursively calling encode-symbol for that branch. Oh, and we'll also need a base case... Once we reach a leaf node we have no further children to navigate, so we can simply return the empty list.

This gives us the following implementation:

(define (encode-symbol symbol tree)
  (cond ((not (memq symbol (symbols tree)))
         (error "bad symbol -- ENCODE-SYMBOL" symbol))
        ((leaf? tree) '())
        ((memq symbol (symbols (left-branch tree)))
         (cons 0 (encode-symbol symbol (left-branch tree))))
        ((memq symbol (symbols (right-branch tree)))
         (cons 1 (encode-symbol symbol (right-branch tree))))))

Let's see it in action:

> (encode '(A D A B B C A) sample-tree)
'(0 1 1 0 0 1 0 1 0 1 1 1 0)

SICP Exercise 2.67: Decoding a Message

Define an encoding tree and a sample message:

(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                   (make-leaf 'B 2)
                   (make-code-tree (make-leaf 'D 1)
                                   (make-leaf 'C 1)))))

(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))

Use the decode procedure to decode the message, and give the result.

Okay, let's stick it in the interpreter and see what we get:

> (decode sample-message sample-tree)
'(A D A B B C A)

SICP Exercise 2.66: Looking up Data

Implement the lookup procedure for the case where the set of records is structured as a binary tree, ordered by the numerical values of the keys.

First, let's define our record structure. To keep it simple, a record will be a list, with the numerical value of the key held at the head of the list. This means we can define key as follows:

(define (key record)
  (car record))

Then we can simply take element-of-set? and make the following modifications to it:

• Instead of checking whether the entry matches the required value, it will check whether the value returned by applying key to the entry matches the requested key.
• If it finds the requested entry then, instead of returning true, it will return the entry itself.
• The recursive calls will need to pass the requested key through.
• To save us having to extract the key of the entry of the current node each time, if the current node isn't null then we'll extract it once.

Here's element-of-set? again as a reminder:

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (entry set)) true)
        ((< x (entry set))
         (element-of-set? x (left-branch set)))
        ((> x (entry set))
         (element-of-set? x (right-branch set)))))

...and here's my version of lookup:

(define (lookup given-key set-of-records)
  (if (null? set-of-records)
      #f
      (let ((entry-key (key (entry set-of-records))))
        (cond ((= given-key entry-key) (entry set-of-records))
              ((< given-key entry-key)
               (lookup given-key (left-branch set-of-records)))
              ((> given-key entry-key)
               (lookup given-key (right-branch set-of-records)))))))

Right, let's put it to the test:

         
> (define records (list->tree '((1 one) (2 two) (4 four) (5 five) (7 seven) (10 ten))))
> records
'((4 four) ((1 one) () ((2 two) () ())) ((7 seven) ((5 five) () ()) ((10 ten) () ())))
> (lookup 1 records)
'(1 one)
> (lookup 4 records)
'(4 four)
> (lookup 7 records)
'(7 seven)
> (lookup 3 records)
#f