問題解答

問2.69

(define (successive-merge  trees)
  (if (= (length trees) 1)
      trees
      (letrec* ((l (length trees))
                (carTrees (take trees (- l 2)))
                (cdrTrees (drop trees (- l 2)))
                (leaf (make-code-tree (car cdrTrees) (cadr cdrTrees)))
               (successive-merge (adjoin-set leaf carTrees))
               )
      ))

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

(define pairs (list (list 'A 2)
                    (list 'B 2)
                    (list 'C 1)
                    (list 'D 1)))
(define hTree (generate-huffman-tree pairs))
(define code (encode '(A D A B B C A) hTree))
(decode code hTree)

Lisp への信心が足りなさすぎて、処理をコードに落とすところでものすごく時間がかかっちゃいます。

細かい処理で時間をとられがちなので、letrec* とか take とか drop とか、SICP では言及されてないけど存在する便利機能も今後はある程度調べて使っていこうかと思います。

ちなみに解答例は違うアプローチ。

(define (successive-merge set)
 (if (= (length set) 1) (car set)
     (let ((sorted-set (sort set (lambda (x y) (< (weight x) (weight y))))))
       (successive-merge 
        (cons (make-code-tree (car sorted-set) (cadr sorted-set))
              (cddr sorted-set))))))

ソートして、頭から繋げていくのか。たしかにこっちの方が自然ですよね、、、、