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)