SICP по-русски

Очень показательное упражнение, которое одновременно является достаточно простым. SICP продолжает радовать.

Итак, как будут выглядеть операции проверки принадлежности множеству, добавления элемента, пересечения и объединения множеств в случае, если элементы в списке, представляющем множество, могут повторяться?

Во-первых, я хочу заметить, что мы можем вообще ничего не менять: старые операции работают корректно и на новом представлении множеств. Но это не единственный способ задать операции для такого внутреннего представления. Мы можем более вольно обращаться с операциями, создающими большие множества из меньших. Я имею в виду операции adjoin-set и union-set. Если операции element-of-set? и intersection-set мы оставим без изменений, то  adjoin-set и union-set можно сильно упростить, аж до неприличия:

(define (adjoin-set x set)
  (cons x set))

(define (union-set set1 set2)
  (append set1 set2))

Это упрощение возможно из-за того, что нас теперь не заботит многократное повторение одинаковых элементов в списке.

Естественно, за такое упрощение в одном месте приходится расплачиваться в другом. Списки, в которых разрешены повторяющиеся элементы, растут при одинаковых операциях сильнее, чем списки с уникальными элементами.  А значит операции с тем же порядком роста будут выполняться дольше, чем раньше.

Число шагов, требующихся для операций element-of-set?, пропорционально числу элементов, то же можно сказать и о union-set (выигрыш по сравнению с квадратичным числом шагов ранее). Процедура intersection-set, по-прежнему, требует числа шагов, пропорционального квадрату длины списка (только вот длина его теперь будет больше). Наконец, adjoin-set выполняется за константное число шагов (большой выигрыш).

Итак, мы выигрываем в скорости операций adjoin-set и union-set, но проигрываем на операциях element-of-set? и intersection-set.

Таким образом представление множеств в виде списков с повторяющимися элементами имеет смысл тогда, когда операции добавления элемента и объединения множеств производятся часто, а проверка принадлежности элемента множеству и пересечение множеств производятся редко.