Абельсон Х., Сассман Д.Д. Структура и интерпретация компьютерных программ

Подождите немного. Документ загружается.

2.2. Иерархические данные и свойство замыкания

111

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

Определите процедуру last-pair, которая возвращает список, содержащий только последний

элемент данного (непустого) списка.

(last-pair (list 23 72 149 34))

(34)

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

Определите процедуру reverse, которая принимает список как аргумент и возвращает список,

состоящий из тех же элементов в обратном порядке:

(reverse (list 1 4 9 16 25))

(25 16 9 4 1)

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

Рассмотрим программу подсчета способов размена из раздела 1.2.2. Было бы приятно иметь воз-

можность легко изменять валюту, которую эта программа использует, так, чтобы можно было,

например, вычислить, сколькими способами можно разменять британский фунт. Эта программа

написана так, что знание о валюте распределено между процедурами first-denomination и

count-change (которая знает, что существует пять видов американских монет). Приятнее было

бы иметь возможность просто задавать список монет, которые можно использовать при размене.

Мы хотим переписать процедуру cc так, чтобы ее вторым аргументом был список монет, а не

целое число, которое указывает, какие монеты использовать. Тогда у нас могли бы быть списки,

определяющие типы валют:

(define us-coins (list 50 25 10 5 1))

(define uk-coins (list 100 50 20 10 5 2 1 0.5))

Можно было бы вызывать cc следующим образом:

(cc 100 us-coins)

292

Это потребует некоторых изменений в программе cc. Ее форма останется прежней, но со вторым

аргументом она будет работать иначе, вот так:

(define (cc amount coin-values)

(cond ((= amount 0) 1)

((or (< amount 0) (no-more? coin-values)) 0)

(else

(+ (cc amount

(except-first-denomination coin-values))

(cc (- amount

(first-denomination coin-values))

coin-values)))))

Определите процедуры first-denomination, except-first-denomination и no-more? в

терминах элементарных операций над списковыми структурами. Влияет ли порядок списка coin-

values на результат, получаемый cc? Почему?

112

Глава 2. Построение абстракций с помощ ью данных

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

Процедуры +, * и list принимают произвольное число аргументов. Один из способов опреде-

ления таких процедур состоит в использовании точечной записи (dotted-tail notation). В опре-

делении процедуры список параметров с точкой перед именем последнего члена означает, что,

когда процедура вызывается, начальные параметры (если они есть) будут иметь в качестве значе-

ний начальные аргу менты, как и обычно, но значением последнего параметра будет список всех

оставшихся аргументов. Например, если дано определение

(define (f x y . z) hтелоi)

то процедуру f можно вызывать с двумя и более аргументами. Если мы вычисляем

(f 1 2 3 4 5 6)

то в теле f переменная x будет равна 1, y будет равно 2, а z будет списком (3 4 5 6). Если дано

определение

(define (g . w) hтелоi)

то процедура g может вызываться с нулем и более аргументов. Если мы вычислим

(g 1 2 3 4 5 6)

то в теле g значением пер еменной w будет список (1 2 3 4 5 6)

Используя эту нотацию, напишите процедуру same-parity, которая принимает одно или

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

первого аргумента. Например,

(same-parity 1 2 3 4 5 6 7)

(1 3 5 7)

(same-parity 2 3 4 5 6 7)

(2 4 6)

Отображение списков

Крайне полезной операцией является применение какого-л ибо преобразования к каж-

дому элементу списка и порождение списка р е зультатов. Например, следующая проце-

дура умножает каждый элемент списка на заданное число.

(define (scale-list items factor)

(if (null? items)

nil

(cons (* (car items) factor)

(scale-list (cdr items) factor))))

(scale-list (list 1 2 3 4 5) 10)

(10 20 30 40 50)

Для того, чтобы определить f и g при помощи lambda, надо было бы написать

(define f (lambda (x y . z) hтелоi))

(define g (lambda w hтелоi))

2.2. Иерархические данные и свойство замыкания

113

Мы можем выделить здесь общую идею и зафиксировать ее как схему, выраженную

в виде процедуры высшего порядка, в точности как в разделе 1.3. Здесь эта процедура

высшего порядка называе тся map. Map берет в качестве аргументов процедуру от од-

ного аргумента и список, а возвращает список результатов, полученн ых применением

процедуры к каждому элементу списка

(define (map proc items)

(if (null? items)

nil

(cons (proc (car items))

(map proc (cdr items)))))

(map abs (list -10 2.5 -11.6 17))

(10 2.5 11.6 17)

(map (lambda (x) (* x x))

(list 1 2 3 4))

(1 4 9 16)

Теперь мы можем дать новое определение scale-list через map:

(define (scale-list items factor)

(map (lambda (x) (* x factor))

items))

Map является важным конструктом, не только потому, что она фиксирует общую

схему, но и потому, что она повышает уровень абстракции при работе со списками. В

исходном определении scale-list рекур сивная структура программы привлекает вни-

мание к поэлементной обработке списка. Определение scale-list через map устраня-

ет этот уровень деталей и подчерки вает, что умножение преобразует список элементов

в список результатов. Разница между этими двумя определени ями состоит не в том,

что компьютер выполняет другой процесс (это не так), а в том, что м ы думаем об этом

процессе по-другому. В сущности, map помогает установить барьер абстракции, который

отделяет реализацию процедур, преобразующих списки, от деталей того, как выбираются

и комбинируются элементы списков. Подобно барьерам на рисунке 2.1, эта абстракция

позволяет нам свободно изменять низкоуровневые детали того, как реализованы списки,

сохраняя концептуальную схему с операциями, переводящими одни последовательности

Стандартная Scheme содержит более общую процедуру map, чем описанная здесь. Этот вариант map

принимает процедуру от n аргументов и n списков и применяет процедуру ко всем первым элементам списков,

всем вторым элементам списков и так далее. Возвращается список результатов. Например:

(map + (list 1 2 3) (list 40 50 60) (list 700 800 900))

(741 852 963)

(map (lambda (x y) (+ x (* 2 y)))

(list 1 2 3)

(list 4 5 6))

(9 12 15)

114

Глава 2. Построение абстракций с помощ ью данных

в другие . В разделе 2.2.3 такое использование последовательностей к ак способ органи-

зации программ рассматривается более подробно.

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

Процедура square-list принимает в качестве аргумента список чисел и возвращает список

квадратов этих чисел.

(square-list (list 1 2 3 4))

(1 4 9 16)

Перед Вами два различных определения square-list. Закончите их, вставив пропущенные вы-

ражения:

(define (square-list items)

(if (null? items)

nil

(cons h??i h??i)))

(define (square-list items)

(map h??i h??i))

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

Хьюго Дум пытается переписать первую из процедур square-list из упражнения 2.21 так,

чтобы она работала как итеративный процесс:

(define (square-list items)

(define (iter things answer)

(if (null? things)

answer

(iter (cdr things)

(cons (square (car things))

answer))))

(iter items nil))

К сожалению, такое определение square-list выдает список результатов в порядке, обратном

желаемому. Почему?

Затем Хьюго пытается исправить ошибку, обменяв аргументы cons:

(define (square-list items)

(define (iter things answer)

(if (null? things)

answer

(iter (cdr things)

(cons answer

(square (car things))))))

(iter items nil))

И так программа тоже не раб отает. Объясните это.

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

Процедура for-each похожа на map. В качестве аргументов она принимает процедуру и спи-

сок элементов. Однако вместо того, чтобы формировать список результатов, for-each просто

2.2. Иерархические данные и свойство замыкания

115

(1 2)

3 4

(3 4)

((1 2) 3 4)

Рис. 2.5. Структура, формируемая (cons (list 1 2) (list 3 4))

применяет процедуру по очер еди ко всем элементам слева направо. Результаты применения про-

цедуры к аргументам не используются вообще — for-each применяют к процедурам, которые

осуществляют какое-либо действие вроде печати. Например,

(for-each (lambda (x) (newline) (display x))

(list 57 321 88))

321

Значение, возвращаемое вызовом for-each (оно в листинге не показано) может быть каким

угодно, например истина. Напишите реализацию for-each.

2.2.2. Иерархические структуры

Представление последовательностей в виде списков естественно распространить на

последовательности, элементы которых сами могут быть последовательностями . Напри-

мер, мы можем рассматривать объект ((1 2) 3 4), получаемый с помощ ью

(cons (list 1 2) (list 3 4))

как список с тремя членами, первый из которых сам является списком. В сущности, это

подсказывается формой, в которой результат печатается интерпретатором . Рисунок 2.5

показывает представление этой структуры в терминах пар.

Еще один способ думать о последовательностях последовательностей — деревья

(tree s). Элементы последовательности являются ветвями дерева, а элементы, которые

сами по себе последовательности — поддеревьями. Рисунок 2.6 показывает структуру,

изображенную на рис. 2.5, в виде дерева.

Естественным инструментом для работы с деревьями является рекурсия, поскольку

часто можно свести операции над деревьями к операциям над их ветвями, которые сами

сводятся к операция м над ветвями ветвей, и так далее, пока мы не достигнем листьев

дерева. Например, сравним процедуру length из раздела 2.2.1 с процедурой count-

leaves, которая подсчитывает число листьев дерева:

116

Глава 2. Построение абстракций с помощ ью данных

(1 2)

((1 2) 3 4)

Рис. 2.6. Списковая структура с рис. 2.5, рассматриваемая как дерево.

(define x (cons (list 1 2) (list 3 4)))

(length x)

(count-leaves x)

(list x x)

(((1 2) 3 4) ((1 2) 3 4))

(length (list x x))

(count-leaves (list x x))

Чтобы реализовать count-leaves, вспомним рекурсивную схему вычисления length:

• Длина списка x есть 1 плюс длина cdr от x.

• Длина пустого списка есть 0.

Count-leaves очень похожа на эту схему. Значение для пустого списка остается

тем же:

• Count-leaves от пустого списка равна 0.

Однако в шаге редукции, когда мы выделяем car списка, нам нужно учесть, что

car сам по себе может быть деревом, листья которого нам требуется сосчитать. Таким

образом, шаг редукции таков:

• Count-leaves от дерева x есть count-leaves от (car x) плюс count-

leaves от (cdr x).

Наконец, вычисляя car-ы, мы достигаем листьев, так что нам требуется еще один

базовый случай:

• Count-leaves от листа равна 1.

2.2. Иерархические данные и свойство замыкания

117

Писать рекурсивные процедуры над деревьями в Scheme помогает элементарный пре-

дикат pair?, который проверяет, является ли его аргумент парой. Вот процедура цели-

ком

(define (count-leaves x)

(cond ((null? x) 0)

((not (pair? x)) 1)

(else (+ (count-leaves (car x))

(count-leaves (cdr x))))))

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

Предположим, мы вычисляем выражение (list 1 (list 2 (list 3 4))). Укажите, какой

результат напечатает интерпретатор, изобразите его в виде стрелочной диаграммы, а также его

интерпретацию в виде дерева (как на рисунке 2.6).

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

Укажите комбинации car и cdr, которые извлекают 7 из следующих списков:

(1 3 (5 7) 9)

((7))

(1 (2 (3 (4 (5 (6 7))))))

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

Допустим, мы определили x и y как два списка:

(define x (list 1 2 3))

(define y (list 4 5 6))

Какой результат напечатает интерпретатор в ответ на следующие выражения:

(append x y)

(cons x y)

(list x y)

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

Измените свою процедуру reverse из упражнения 2.18 так, чтобы получилась процедура deep-

reverse, которая принимает список в качестве аргумента и возвращает в качестве значения

список, где порядок элементов обратный и подсписки также обращены. Например:

(define x (list (list 1 2) (list 3 4)))

((1 2) (3 4))

(reverse x)

((3 4) (1 2))

(deep-reverse x)

((4 3) (2 1))

Порядок первых двух ветвей существен, поскольку пустой список удовлетворяет предикату null? и при

этом не является парой.

118

Глава 2. Построение абстракций с помощ ью данных

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

Напишите процедуру fringe, которая берет в качестве аргумента дерево (представленное в ви-

де списка) и возвращает список, элементы которого — все лис тья дерева, упорядоченные слева

направо. Например,

(define x (list (list 1 2) (list 3 4)))

(fringe x)

(1 2 3 4)

(fringe (list x x))

(1 2 3 4 1 2 3 4)

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

Бинарный мобиль состоит из двух ветвей, левой и правой. Каждая ветвь представляет собой

стержень определенной длины, с которого свисает либо гирька, либ о еще один бинарный мобиль.

Мы можем представить бинарный мобиль в виде составных данных, соединив две ветви (например,

с помощью list):

(define (make-mobile left right)

(list left right))

Ветвь составляется из длины length (которая должна быть числом) и структуры structure,

которая может быть либо числом (представляющим простую гирьку), либо еще одним мобилем:

(define (make-branch length structure)

(list length structure))

а. Напишите соответствующие селекторы left-branch и right-branch, которые возвраща-

ют левую и правую ветви мобиля, а также branch-length и branch-structure, которые

возвращают компоненты ветви.

б. С помощью этих селекторов напишите процедуру total-weight, которая возвращает общий

вес мобиля.

в. Говорят, что мобиль сбалансирован, если момент вращения, действующий на его левую ветвь,

равен моменту вращения, действующему на правую ветвь (то есть длина левого стержня, умножен-

ная на вес груза, свисающего с него , равна соответствующему произведению для правой стороны),

и если все подмобили, свисающие с его ветвей, также сбалансированы. Нап ишите предикат, кото-

рый проверяет мобили на сбалансированность.

г. Допустим, мы изменили представление мобилей, так что конструкторы теперь приняли такой

вид:

(define (make-mobile left right)

(cons left right))

(define (make-branch length structure)

(cons length structure))

Как много Вам нужно изменить в программах, чтобы перейти на новое представление?

2.2. Иерархические данные и свойство замыкания

119

Отображение деревьев

Подобно тому, как map может служить мощной абстракцией для работы с последова-

тельностями, map, совмещенная с рекурсией, служит мощной абстракцией для работы с

деревьями. Например, процедура scale-tree, аналогичная процедуре scale-list из

раздела 2.2.1, принимает в качестве аргумента числовой множитель и дерево, листьями

которого являются числа. Она возвращает дерево той же формы, где каждое число умно-

жено на множитель. Рекурсивная схема scale-tree похожа на схему count-leaves:

(define (scale-tree tree factor)

(cond ((null? tree) nil)

((not (pair? tree)) (* tree factor))

(else (cons (scale-tree (car tree) factor)

(scale-tree (cdr tree) factor)))))

(scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))

10)

(10 (20 (30 40) 50) (60 70))

Другой способ ре ализации scale-tree состоит в том, чтобы рассматривать дерево

как последовательность поддеревьев и использовать map. М ы о тображаем последова-

тельность, масштабируя по очереди каждое поддерево, и возвращаем список результатов.

В базовом случае, когда дер ево является листом, мы просто умножаем:

(define (scale-tree tree factor)

(map (lambda (sub-tree)

(if (pair? sub-tree)

(scale-tree sub-tree factor)

(* sub-tree factor)))

tree))

Многие операци и над деревьями могут быть реализованы с помощью такого сочетания

операций над последовательностями и рекурсии.

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

Определите процедуру square-tree, подобную процедуре square-list из упражнения 2.21. А

именно, square-tree должна вести себя следующим образом:

(square-tree

(list 1

(list 2 (list 3 4) 5)

(list 6 7)))

(1 (4 (9 16) 25) (36 49))

Определите square-tree как прямо (то есть без использования процедур высших порядков), так

и с помощью map и рекурсии.

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

Абстрагируйте свой ответ на упражнение 2.30, получая процедуру tree-map, так, чтобы square-

tree можно было определить следующим образом:

120

Глава 2. Построение абстракций с помощ ью данных

(define (square-tree tree) (tree-map square tree))

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

Множество можно представить как список его различных элементов, а множество его подмножеств

как список списков. Например, если множество равно (1 2 3), то множество его подмножеств

равно (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Закончите следующее определение

процедуры, которая порождает множество подмножеств и дайте ясное объяснение, почему она

работает:

(define (subsets s)

(if (null? s)

(list nil)

(let ((rest (subsets (cdr s))))

(append rest (map h??i rest)))))

2.2.3. Последовательности как стандартные интерфейсы

При работе с составными данными мы подчеркивали, что абстракция позволяет про-

ектировать программы, не увязая в де талях представления данных, и оставляет возмож-

ность экспериментировать с различными способами представления. В этом разделе мы

представляем еще один мощный принцип проектирования для работы со структурами

дан ных — использование стандартных интерфейсов (conventional interfaces).

В разделе 1.3 мы видели, как абстракции, реализованные в виде процедур высших

порядков, спосо бны выразить общие схемы программ, ко торые работают с числовыми

дан ными. Наша способность формулировать подобные операции с составн ыми данными

существен ным образом зависит от того, в каком стиле мы манипулируем своими струк-

турами данных. Например, рассмотрим следующую процедуру, аналогичную count-

leaves из раздела 2.2.2. Она принимает в каче стве аргумента дерево и вычисляет

сумму квадратов тех из его листьев, которые являются нечетными числами:

(define (sum-odd-squares tree)

(cond ((null? tree) 0)

((not (pair? tree))

(if (odd? tree) (square tree) 0))

(else (+ (sum-odd-squares (car tree))

(sum-odd-squares (cdr tree))))))

При поверхностном взгляде кажется, что эта процедура очень сильно отличается от

следующей, которая строит список всех четных чисел Фибоначчи Fib(k), где k меньше

или равно данного целого числа n:

(define (even-fibs n)

(define (next k)

(if (> k n)

nil

(let ((f (fib k)))

(if (even? f)

(cons f (next (+ k 1)))

(next (+ k 1))))))

(next 0))