SICP по-русски

На самом деле построить процедуру successive-merge совсем не сложно. Алгоритм наших действий прост. Мы будем хранить все деревья и листья в упорядоченном по возрастанию веса списке. Раз так, два самых легких элемента всегда будут находиться на двух первых позициях в списке. Стало быть, нам достаточно на каждом этапе алгоритма последовательного слияния брать два первых элемента из списка, соединять их в один и возвращать полученное дерево обратно в список (при этом оно в нем займет место в соответствии со своим весом, то есть список сохранит свойство упорядоченности). На каждом шаге количество элементов в списке уменьшается на один. Заканчиваем слияния мы тогда, когда в списке остался ровно один элемент, который и является искомым деревом Хаффмана.

Процедура successive-merge, реализующая эту идею, представлена ниже:

(define (successive-merge trees)
  (if (null? (cdr trees))
      (car trees)
      (successive-merge (adjoin-set (make-code-tree (car trees)
                                                    (cadr trees))
                                    (cddr trees)))))

Определение не лишено некоторой элегантности.