SICP по-русски

Вчера этому ресурсу незаметно (я чуть было не пропустил такое знаменательное событие) стукнуло полгода. Первая заметка датирована 12 августа 2007 года.
На текущий момент статистика следующая:

Написано 137 заметок (включая эту). К заметкам создано 57 комментариев.
Решено 112 упражнений (это меньше упражнения в день в среднем, но в последний месяц я сильно улучшил статистику и буду стараться поддерживать […]

Просто возьмем процедуру element-of-set? для множеств, представленных бинарными деревьями, и модернизируем ее для работы с записями с числовым ключом. Также учтем, что lookup не только проверяет присутствие записи с заданным ключом, но и возвращает саму эту запись в случае успешного поиска.
Получим следующую процедуру:
(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) false)
        ((= given-key (key (entry set-of-records)))
         […]

Процедуры tree->list (я не буду использовать индексы 1 и 2) и list->tree дают нам возможность свободно преобразовывать множества, представленные упорядоченными списками и (сбалансированными) бинарными деревьями, из одного представления в другое за линейное (Θ(n)) число операций.
Это позволяет нам реализовать операции над множествами, представленными бинарными деревьями, через уже реализованные операции над множествами, представленными упорядоченными списками. Для этого […]

Алгоритм работы процедуры partial-tree может быть очень кратко описан следующим образом.
Мы выбираем в списке центральный элемент и разбиваем список на часть до него не включительно (левая часть), сам элемент и часть после него опять не включительно (правая часть). После этого мы строим дерево, корнем которого является выбранный центральный элемент, левое поддерево строится аналогичным образом по […]

Процедуры tree->list-1 и tree->list-2 создают отсортированный список элементов в дереве (фактически, они производят обход дерева в глубину слева направо и собирают значения entry каждого узла дерева в список). Таким образом они делают одно и то же. Разница между ними в том, что tree->list-1 записана в форме, порождающей рекурсивный процесс, а tree->list-2 порождает итеративный процесс.
Поскольку все деревья на […]

Идея реализации union-set за линейный проход абсолютно аналогична идее, положенной в основу intersection-set из книги. Мы движемся параллельно по двум спискам и сравниваем их текущие первые элементы. Если они равны, мы решаем задачу для хвостов списков и приписываем любой из двух равных головных элементов в начало. Если же один из элементов меньше другого, то его […]

Для того, чтобы получить уменьшение вдвое числа шагов, необходимого для добавления элемента во множество, представленное в виде неупорядоченного списка, нам недостаточно просто определить, есть ли элемент во множестве с помощью element-of-set?, а затем добавить его подобно тому, как мы делали для множеств, представленных неупорядоченными списками. В этом случае поиск и вставка потребуют в среднем по […]

Очень показательное упражнение, которое одновременно является достаточно простым. SICP продолжает радовать.
Итак, как будут выглядеть операции проверки принадлежности множеству, добавления элемента, пересечения и объединения множеств в случае, если элементы в списке, представляющем множество, могут повторяться?
Во-первых, я хочу заметить, что мы можем вообще ничего не менять: старые операции работают корректно и на новом представлении множеств. Но это не единственный […]

Для реализации операции объединения множеств мы можем применить рекурсивную стратегию, близкую по задумке к той, которая приводится при описании операции пересечения множеств в тексте книги. А именно, воспользуемся следующими тремя правилами при объединении множеств set1 и set2:

Если set1 пусто, то объединение set1 и set2 есть set2.
Если элемент x из set1 содержится в set2, то объединение set1 и set2 - это то же, что и объединение set1 […]

Начнем с более простой части А упражнения. При записи в инфиксной форме с расстановкой всех скобок операции сложения и умножения принимают всегда по два аргумента. Причем порядок следования элементов в списке всегда такой: первый аргумент, знак операции, второй аргумент.
Таким образом мы сразу же достаточно прямолинейным способом получаем определения предикатов, селекторов и конструкторов (в конструкторах […]