(deriv (* x y (+ x 3)) x)

Попытайтесь сделать это, изменяя только представление сумм и произведений, не трогая процедуру deriv. Тогда, например, процедура addend будет возвращать первое слагаемое суммы, а augend сумму остальных.

Упражнение 2.58.

Предположим, что нам захотелось изменить программу дифференцирования так, чтобы она работала с обычной математической нотацией, где + и * не префиксные, а инфиксные операции. Поскольку программа взятия производных определена в терминах абстрактных данных, мы можем изменять представление выражений, с которыми она работает, меняя только предикаты, селекторы и конструкторы, определяющие представление алгебраических выражений, с которыми должен работать дифференциатор.

a.Покажите, как это сделать так, чтобы брать производные от выражений, представленных в инфиксной форме, например (x + (3 * (x + (y + 2)))) . Для упрощения задачи предположите, что + и * всегда принимают по два аргумента, и что в выражении расставлены все скобки.

b.Задача становится существенно сложней, если мы разрешаем стандартную алгебраическую нотацию, например (x + 3 * (x + y + 2)) , которая опускает ненужные скобки и предполагает, что умножение выполняется раньше, чем сложение. Можете ли Вы разработать соответствующие предикаты, селекторы и конструкторы для этой нотации так, чтобы наша программа взятия производных продолжала работать?

2.3.3 Пример: представление множеств

В предыдущих примерах мы построили представления для двух типов составных объектов: для рациональных чисел и для алгебраических выражений. В одном из этих примеров перед нами стоял выбор, упрощать ли выражение при его конструировании или при обращении; в остальном же выбор представления наших структур через списки был простым делом. Когда мы обращаемся к представлению множеств, выбор представления не так очевиден. Здесь существует несколько возможных представлений, и они значительно отличаются друг от друга в нескольких аспектах.

Говоря неформально, множество есть просто набор различных объектов. Чтобы дать ему более точное определение, можно использовать метод абстракции данных. А именно, мы определяем «множество», указывая операции, которые можно производить над множествами. Это операции union-set (объединение), intersection-set (пересечение), element-of-set? (проверка на принадлежность) и adjoin-set (добавление элемента). Element-of-set? - это предикат, который определяет, является ли данный объект элементом множества. Adjoin-set принимает как аргументы объект и множество, и возвращает множество, которое содержит все элементы исходного множества плюс добавленный элемент. Union-set вычисляет объединение двух множеств, то есть множество, содержащее те элементы, которые присутствуют хотя бы в одном из аргументов. Intersection-set вычисляет пересечение двух множеств, то есть множество, которое содержит только те элементы, которые присутствуют в обоих аргументах. С точки зрения абстракции данных, мы имеем право взять любое представление, позволяющее нам использовать эти операции

способом, который согласуется с вышеуказанной интерпретацией.37

Множества как неупорядоченные списки

Можно представить множество как список, в котором ни один элемент не содержится более одного раза. Пустое множество представляется пустым списком. При таком представлении element-of-set? подобен процедуре memq из раздела 2.3.1. Она использует не eq?, а equal?, так что элементы множества не обязаны быть символами:

(define (element-of-set? x set) (cond ((null? set) false)

((equal? x (car set)) true)

(else (element-of-set? x (cdr set)))))

Используя эту процедуру, мы можем написать adjoin-set. Если объект, который требуется добавить, уже принадлежит множеству, мы просто возвращаем исходное множество. В противном случае мы используем cons, чтобы добавить объект к списку. представляющему множество:

(define (adjoin-set x set) (if (element-of-set? x set) set

(cons x set)))

Для intersection-set можно использовать рекурсивную стратегию. Если мы знаем, как получить пересечение set2 и cdr от setl, нам нужно только понять, надо ли добавить к нему car от setl. Это зависит от того, принадлежит ли (car setl) еще и set2. Получается такая процедура:

(define (intersection-set setl set2)

(cond ((or (null? setl) (null? set2)) ())

((element-of-set? (car setl) set2) (cons (car setl)

(intersection-set (cdr setl) set2))) (else (intersection-set (cdr setl) set2))))

Один из вопросов, которые должны нас заботить при разработке реализации - эффективность. Рассмотрим число шагов, которые требуют наши операции над множествами. Поскольку все они используют element-of-set?, скорость этой операции оказывает большое влияние на скорость реализации

37Если нам хочется быть более формальными, мы можем определить «соответствие вышеуказанной интерпретации» как условие, что операции удовлетворяют некоторому набору правил вроде следующих:

•Для любого множества S и любого объекта x, (element-of-set? x (adjoin-set x S)) истинно (неформально: «добавление объекта к множеству дает множество, содержащее этот объект»).

•Для любых двух множеств S и T и любого объекта x, (element-of-set? x (union-set S T)) равно (or (element-of-set? x S) (element-of-set? x T)) (неформально: «элементы (union-set ST) - это те элементы, которые принадлежат либо S, либо T»).

•Для любого объекта x, (element-of-set? x ()) ложно (неформально: «ни один объект не принадлежит пустому множеству»).

в целом. Теперь заметим, что для того, чтобы проверить, является ли объект элементом множества, процедуре element-of-set? может потребоваться просмотреть весь список. (В худшем случае оказывается, что объекта в списке нет.) Следовательно, если в множестве n элементов, element-of-set? может затратить до n шагов. Таким образом, число требуемых шагов растет как 0(n). Число шагов, требуемых adjoin-set, которая эту операцию использует, также растет как 0(n). Для intersection-set, которая проделывает element-of-set? для каждого элемента set1, число требуемых шагов растет как произведение размеров исходных множеств, или 0(n2) для двух множеств размера n. То же будет верно и для union-set.

Упражнение 2.59.

Реализуйте операцию union-set для представления множеств в виде неупорядоченных списков.

Упражнение 2.60.

Мы указали, что множество представляется как список без повторяющихся элементов. Допустим теперь, что мы разрешаем повторяющиеся элементы. Например, множество {1, 2, 3} могло бы быть представлено как список (2 3 2 1 3 2 2). Разработайте процедуры element-of-set?, adjoin-set, union-set и intersection-set, которые бы работали с таким представлением. Как соотносится эффективность этих операций с эффективностью соответствующих процедур для представления без повторений? Существуют ли приложения, в которых Вы бы использовали скорее это представление, чем представление без повторений?

Множества как упорядоченные списки

Один из способов ускорить операции над множествами состоит в том, чтобы изменить представление таким образом, чтобы элементы множества перечислялись в порядке возрастания. Для этого нам потребуется способ сравнения объектов, так, чтобы можно было сказать, какой из них больше. Например, символы мы могли бы сравнивать лексикографически, или же мы могли бы найти какой-нибудь способ ставить каждому объекту в соответствие некоторое уникальное число и затем сравнивать объекты путем сравнения соответствующих чисел. Чтобы упростить обсуждение, мы рассмотрим только случай, когда элементами множества являются числа, так что мы сможем сравнивать элементы при помощи > и <. Мы будем представлять множество чисел как список его элементов в возрастающем порядке. В то время как первая наша реализация позволяла нам представлять множество {1,3,6,10} путем перечисления его элементов в произвольном порядке, в новом представлении разрешен только список (1 3 6 10).

Одно из преимуществ упорядочения проявляется в element-of-set?: проверяя наличие элемента, нам больше незачем просматривать все множество. Если мы достигли элемента, который больше того объекта, который мы ищем, мы можем уже сказать, что искомого в списке нет:

(define (element-of-set? x set) (cond ((null? set) false)

((= x (car set)) true)

((< x (car set)) false)

(else (element-of-set? x (cdr set)))))