SICP問題2.68

教科書で定義されている encode 手続き

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

encode-symbolの定義

(define (include-symbol? symbol tree)
  (define (iter symbol-list)
    (if (null? symbol-list)
	#f
	(if (eq? symbol (car symbol-list))
	    #t
	    (iter (cdr symbol-list)))))
  (iter (symbols tree))
)
(define (encode-symbol symbol tree)
  (define (iter bits sub-tree)
    (if (leaf? sub-tree)
	bits
	(if (include-symbol? symbol (left-branch sub-tree))
	    (iter (append bits (list 0)) (left-branch sub-tree))
	    (iter (append bits (list 1)) (right-branch sub-tree)))))
  (if (include-symbol? symbol tree)
      (iter () tree)
      (error "bad symbold (Not in tree)")))

あんまり綺麗じゃないなぁ。
一応、テスト。

(encode '(A D A B B C A) sample-tree)
; (0 1 1 0 0 1 0 1 0 1 1 1 0)
sample-message
; (0 1 1 0 0 1 0 1 0 1 1 1 0)
(decode sample-message sample-tree)
; (A D A B B C A)
(encode '(A D A B B C A) sample-tree)
; (0 1 1 0 0 1 0 1 0 1 1 1 0)

OK。
iterの数を減らしてちょっと書き直し。

(define (encode-symbol symbol tree)
  (define (iter sub-tree)
    (if (leaf? sub-tree)
	()
	(if (include-symbol? symbol (left-branch sub-tree))
	    (cons 0 (iter (left-branch sub-tree)))
	    (cons 1 (iter (right-branch sub-tree))))))
  (if (include-symbol? symbol tree)
      (iter tree)
      (error "bad symbold (Not in tree)")))

それでもイマイチか。