SICP Exercise 2.68

sicp

Question

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.

Answer

(define (encode-symbol symbol tree)
  (let ((left (left-branch tree))
        (right (right-branch tree)))
    (cond ((leaf? tree) '())
          ((element-of-set? symbol (symbols left))
           (cons '0 (encode-symbol symbol left)))
          ((element-of-set? symbol (symbols right))
           (cons '1 (encode-symbol symbol right))))))

This gives the result we expect:

(define sample-message
  '(A D A B B C A))
(encode sample-message sample-tree)

Result:

(0 1 1 0 0 1 0 1 0 1 1 1 0)