(wat-aro)

無職から有職者にランクアップしました

SICP 問題 2.69

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

;; pairsは昇順に並んでいるので先頭の2要素をmake-code-pairsする.
;; それを(cddr pairs)にadjoin-setすればまた昇順に並んだpairsができるのでそれを繰り返す.
(define (successive-merge pairs)
  (if (null? (cdr pairs))
      (car pairs)
      (successive-merge (adjoin-set (make-code-pairs (car pairs)
                                                     (cadr pairs))
                                    (cddr pairs)))))