Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 27
Текст из файла (страница 27)
z) hтелоi))(define g (lambda w hтелоi))2.2. Иерархические данные и свойство замыкания113Мы можем выделить здесь общую идею и зафиксировать ее как схему, выраженнуюв виде процедуры высшего порядка, в точности как в разделе 1.3. Здесь эта процедуравысшего порядка называется map. Map берет в качестве аргументов процедуру от одного аргумента и список, а возвращает список результатов, полученных применениемпроцедуры к каждому элементу списка12 :(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, эта абстракцияпозволяет нам свободно изменять низкоуровневые детали того, как реализованы списки,сохраняя концептуальную схему с операциями, переводящими одни последовательности12 Стандартная 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(3 4)((1 2) 3 4)(1 2)3142Рис.
2.5. Структура, формируемая (cons (list 1 2) (list 3 4))применяет процедуру по очереди ко всем элементам слева направо. Результаты применения процедуры к аргументам не используются вообще — for-each применяют к процедурам, которыеосуществляют какое-либо действие вроде печати. Например,(for-each (lambda (x) (newline) (display x))(list 57 321 88))5732188Значение, возвращаемое вызовом for-each (оно в листинге не показано) может быть какимугодно, например истина. Напишите реализацию for-each.2.2.2.
Иерархические структурыПредставление последовательностей в виде списков естественно распространить напоследовательности, элементы которых сами могут быть последовательностями. Например, мы можем рассматривать объект ((1 2) 3 4), получаемый с помощью(cons (list 1 2) (list 3 4))как список с тремя членами, первый из которых сам является списком. В сущности, этоподсказывается формой, в которой результат печатается интерпретатором. Рисунок 2.5показывает представление этой структуры в терминах пар.Еще один способ думать о последовательностях последовательностей — деревья(trees). Элементы последовательности являются ветвями дерева, а элементы, которыесами по себе последовательности — поддеревьями. Рисунок 2.6 показывает структуру,изображенную на рис.
2.5, в виде дерева.Естественным инструментом для работы с деревьями является рекурсия, посколькучасто можно свести операции над деревьями к операциям над их ветвями, которые самисводятся к операциям над ветвями ветвей, и так далее, пока мы не достигнем листьевдерева. Например, сравним процедуру length из раздела 2.2.1 с процедурой countleaves, которая подсчитывает число листьев дерева:Глава 2. Построение абстракций с помощью данных116((1 2) 3 4)(1 2)3142Рис.
2.6. Списковая структура с рис. 2.5, рассматриваемая как дерево.(define x (cons (list 1 2) (list 3 4)))(length x)3(count-leaves x)4(list x x)(((1 2) 3 4) ((1 2) 3 4))(length (list x x))2(count-leaves (list x x))8Чтобы реализовать count-leaves, вспомним рекурсивную схему вычисления length:• Длина списка x есть 1 плюс длина cdr от x.• Длина пустого списка есть 0.Count-leaves очень похожа на эту схему. Значение для пустого списка остаетсятем же:• Count-leaves от пустого списка равна 0.Однако в шаге редукции, когда мы выделяем car списка, нам нужно учесть, чтоcar сам по себе может быть деревом, листья которого нам требуется сосчитать. Такимобразом, шаг редукции таков:• Count-leaves от дерева x есть count-leaves от (car x) плюс countleaves от (cdr x).Наконец, вычисляя car-ы, мы достигаем листьев, так что нам требуется еще одинбазовый случай:• Count-leaves от листа равна 1.2.2.
Иерархические данные и свойство замыкания117Писать рекурсивные процедуры над деревьями в Scheme помогает элементарный предикат pair?, который проверяет, является ли его аргумент парой. Вот процедура целиком13 :(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 так, чтобы получилась процедура deepreverse, которая принимает список в качестве аргумента и возвращает в качестве значениясписок, где порядок элементов обратный и подсписки также обращены.
Например:(define x (list (list 1 2) (list 3 4)))x((1 2) (3 4))(reverse x)((3 4) (1 2))(deep-reverse x)((4 3) (2 1))13 Порядок первых двух ветвей существен, поскольку пустой список удовлетворяет предикату 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, так, чтобы squaretree можно было определить следующим образом: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)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
