Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 28
Текст из файла (страница 28)
Закончите следующее определениепроцедуры, которая порождает множество подмножеств и дайте ясное объяснение, почему онаработает:(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 мы видели, как абстракции, реализованные в виде процедур высшихпорядков, способны выразить общие схемы программ, которые работают с числовымиданными.
Наша способность формулировать подобные операции с составными даннымисущественным образом зависит от того, в каком стиле мы манипулируем своими структурами данных. Например, рассмотрим следующую процедуру, аналогичную countleaves из раздела 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))2.2.
Иерархические данные и свойство замыкания121enumerate:tree leavesfilter:odd?map:squareaccumulate:+, 0enumerate:integersmap:fibfilter:even?accumulate:cons, ()Рис. 2.7. Диаграммы потока сигналов для процедур sum-odd-squares (сверху) иeven-fibs (снизу) раскрывают схожесть этих двух программ.Несмотря на то, что структурно эти процедуры весьма различны, более абстрактное описание двух процессов вычисления раскрывает немалую долю сходства. Перваяпрограмма• перечисляет листья дерева;• просеивает их, отбирая нечетные;• возводит в квадрат каждое из отобранных чисел; и• накапливает результаты при помощи +, начиная с 0.Вторая программа• перечисляет числа от 1 до n;• вычисляет для каждого из них число Фибоначчи;• просеивает их, выбирая нечетные; и• собирает их с помощью cons, начиная с пустого списка.Специалисту по обработке сигналов покажется естественным выразить эти процессыв терминах сигналов, проходящих через ряд стадий, каждая из которых реализует частьплана программы, как это показано на рисунке 2.7.
В процедуре sum-odd-squaresмы начинаем с перечислителя (enumerator), который порождает «сигнал», состоящий излистьев данного дерева. Этот сигнал пропускается через фильтр (filter), который удаляет все элементы, кроме нечетных. Получившийся после этого сигнал, в свою очередь,проходит отображение (map), которое представляет собой «преобразователь», применяющий к каждому элементу процедуру square. Наконец, выход отображения идет внакопитель (accumulator), который собирает элементы при помощи +, начиная с 0. Дляeven-fibs план аналогичен.К сожалению, два определения процедур, приведенные выше, не отражают эту структуру потока сигналов.
Например, если мы рассмотрим sum-oddsquares, мы обнаружим, что перечисление отчасти реализуется проверками null? и pair?, а отчастидревовидно-рекурсивной структурой процедуры. Подобным образом, накопление отчастипроисходит в проверках, а отчасти в сложении, которое выполняется при рекурсивном122Глава 2. Построение абстракций с помощью данныхвызове.
Вообще, никакая отдельная часть этих процедур не соответствует элементу потоковой диаграммы. Наши две процедуры дробят вычисление другим образом, раскидываяперечисление по программе и смешивая его с отображением, просеиванием и накоплением. Если бы мы смогли организовать свои программы так, чтобы структура обработкипотока сигналов была ясно видна в написанных нами процедурах, то это сделало бысмысл получаемого кода более прозрачным.Операции над последовательностямиИтак, наши программы должны яснее отражать структуру потока сигналов. Ключевым моментом здесь будет перенос внимания на «сигналы», которые передаются от однойстадии процесса к другой. Если мы представим эти сигналы в виде списков, то сможемиспользовать операции над списками, чтобы реализовать обработку на каждом этапе.Например, мы можем реализовать стадии отображения из диаграмм потоков сигналов спомощью процедуры map из раздела 2.2.1:(map square (list 1 2 3 4 5))(1 4 9 16 25)Просеивание последовательности, выбирающее только те элементы, которые удовлетворяют данному предикату, осуществляется при помощи(define (filter predicate sequence)(cond ((null? sequence) nil)((predicate (car sequence))(cons (car sequence)(filter predicate (cdr sequence))))(else (filter predicate (cdr sequence)))))Например,(filter odd? (list 1 2 3 4 5))(1 3 5)Накопление осуществляется посредством(define (accumulate op initial sequence)(if (null? sequence)initial(op (car sequence)(accumulate op initial (cdr sequence)))))(accumulate + 0 (list 1 2 3 4 5))15(accumulate * 1 (list 1 2 3 4 5))120(accumulate cons nil (list 1 2 3 4 5))(1 2 3 4 5)2.2.
Иерархические данные и свойство замыкания123Чтобы реализовать диаграммы потока сигналов, нам остается только перечислитьпоследовательности элементов, с которыми мы будем работать. Для even-fibs нужнопородить последовательность целых чисел в заданном диапазоне. Это можно сделатьтак:(define (enumerate-interval low high)(if (> low high)nil(cons low (enumerate-interval (+ low 1) high))))(enumerate-interval 2 7)(2 3 4 5 6 7)Чтобы перечислить листья дерева, можно использовать такую процедуру14 :(define (enumerate-tree tree)(cond ((null? tree) nil)((not (pair? tree)) (list tree))(else (append (enumerate-tree (car tree))(enumerate-tree (cdr tree))))))(enumerate-tree (list 1 (list 2 (list 3 4)) 5))(1 2 3 4 5)Теперь мы можем переформулировать sum-odd-squares и even-fibs соответственно тому, как они изображены на диаграммах потока сигналов.
В случае sum-oddsquares мы вычисляем последовательность листьев дерева, фильтруем ее, оставляятолько нечетные числа, возводим каждый элемент в квадрат и суммируем результаты:(define (sum-odd-squares tree)(accumulate +0(map square(filter odd?(enumerate-tree tree)))))В случае с even-fibs мы перечисляем числа от 0 до n, порождаем для каждого из нихчисло Фибоначчи, фильтруем получаемую последовательность, оставляя только четныеэлементы, и собираем результаты в список:(define (even-fibs n)(accumulate consnil(filter even?(map fib(enumerate-interval 0 n)))))14 Это в точности процедура fringe из упражнения 2.28.
Здесь мы ее переименовали, чтобы подчеркнуть,что она входит в семейство общих процедур обработки последовательностей.124Глава 2. Построение абстракций с помощью данныхПольза от выражения программ в виде операций над последовательностями состоит втом, что эта стратегия помогает нам строить модульные проекты программ, то есть проекты, которые получаются путем сборки из относительно независимых частей. Можнопоощрять модульное проектирование, давая разработчику набор стандартных компоненти унифицированный интерфейс, предназначенный для гибкого соединения этих компонентов.Модульное построение является мощной стратегией управления сложностью в инженерном проектировании. Например, в реальных приложениях по обработке сигналовпроектировщики обычно строят системы путем каскадирования элементов, которые выбираются из стандартизованных семейств фильтров и преобразователей.
Подобным образом операции над последовательностями составляют библиотеку стандартных элементов,которые мы можем связывать и смешивать. К примеру, можно составить куски из процедур sum-odd-squares и even-fibs и получить программу, которая строит списокквадратов первых n+1 чисел Фибоначчи:(define (list-fib-squares n)(accumulate consnil(map square(map fib(enumerate-interval 0 n)))))(list-fib-squares 10)(0 1 1 4 9 25 64 169 441 1156 3025)Можно переставить куски и использовать их, чтобы вычислить произведение квадратовнечетных чисел в последовательности:(define (product-of-squares-of-odd-elements sequence)(accumulate *1(map square(filter odd? sequence))))(product-of-squares-of-odd-elements (list 1 2 3 4 5))225Часто встречающиеся приложения по обработке данных можно также формулироватьв терминах операций над последовательностями.
Допустим, у нас есть последовательность записей о служащих, и нам требуется найти зарплату самого высокооплачиваемого программиста. Пусть у нас будет селектор salary, который возвращает зарплатуслужащего, и предикат programmer?, который проверяет, относится ли запись к программисту. Тогда мы можем написать:(define (salary-of-highest-paid-programmer records)(accumulate max0(map salary(filter programmer? records))))2.2. Иерархические данные и свойство замыкания125Все эти примеры дают лишь слабое представление об огромной области задач, выразимых в виде операций над последовательностями15.Последовательности, здесь реализованные в виде списков, служат стандартным интерфейсом, который позволяет комбинировать обрабатывающие модули.
Кроме того, еслимы представляем все структуры единым образом как последовательности, то нам удаетсялокализовать зависимость структур данных в своих программах в небольшом наборе операций с последовательностями. Изменяя эти последние, мы можем экспериментировать сразличными способами представления последовательностей, оставляя неприкосновеннойобщую структуру своих программ. Этой возможностью мы воспользуемся в разделе 3.5,когда обобщим парадигму обработки последовательностей и введем бесконечные последовательности.Упражнение 2.33.Заполните пропущенные выражения, так, чтобы получились определения некоторых базовых операций по работе со списками в виде накопления:(define (map p sequence)(accumulate (lambda (x y) h??i) nil sequence))(define (append seq1 seq2)(accumulate cons h??i h??i))(define (length sequence)(accumulate h??i 0 sequence))Упражнение 2.34.Вычисление многочлена с переменной x при данном значении x можно сформулировать в виденакопления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
