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

Модульное построение является мощной стратегией управления сложностью в инженерном проектировании. Например, в реальных приложениях по обработке сигналов проектировщики обычно строят системы путем каскадирования элементов, которые выбираются из стандартизованных семейств фильтров и преобразователей. Подобным образом операции над последовательностями составляют библиотеку стандартных элементов, которые мы можем связывать и смешивать. К примеру, можно составить куски из процедур sum-odd-squares и even-fibs и получить программу, которая строит список квадратов первых n+1 чисел Фибоначчи:

(define (list-fib-squares n) (accumulate cons

nil

(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 max

0

(map salary

(filter programmer? records))))

Все эти примеры дают лишь слабое представление об огромной области задач, выразимых в виде операций над последовательностями.15

15Ричард Уотерс (Waters 1979) разработал программу, которая анализирует традиционные программы на Фортране, представляя их в терминах отображений, фильтров и накоплений. Он обна-

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

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

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

(define (map p sequence)

(accumulate (lambda (x y) {??)) nil sequence))

(define (append seq1 seq2) (accumulate cons {??) {??)))

(define (length sequence)

(accumulate {??) 0 sequence))

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

Вычисление многочлена с переменной x при данном значении x можно сформулировать в виде накопления. Мы вычисляем многочлен

anx + Un-i x + ... + aix + ao

по известному алгоритму, называемому схема Горнера (Horners rule), которое переписывает формулу в виде

(... (anx + an-i)x + ... + ai)x + ao)

Другими словами, мы начинаем с an, умножаем его на x, и так далее, пока не достигнем a0.16 Заполните пропуски в следующей заготовке так, чтобы получить процедуру, которая вычисляет многочлены по схеме Горнера. Предполагается, что коэффициенты многочлена представлены в виде последовательности, от ao до an.

ружил, что 90 процентов кода в Пакете Научных Подпрограмм на Фортране хорошо укладывается в эту парадигму. Одна из причин успеха Лиспа как языка программирования заключается в том, что списки дают стандартное средство представления упорядоченных множеств, с которыми можно работать при помощи процедур высших порядков. Язык программирования APL своей мощности и красоте во многом обязан подобному же выбору. В APL все данные выражаются как массивы, и существует универсальный и удобный набор общих операторов для всевозможных действий над массивами.

16Согласно Кнуту (Knuth 1981), это правило было сформулировано У. Г. Горнером в начале девятнадцатого века, но на самом деле его использовал Ньютон более чем на сто лет раньше. По схеме Горнера многочлен вычисляется с помощью меньшего количества сложений и умножений, чем при прямолинейном способе: вычислить сначала anxn, затем добавить an-1 xn-1 и так далее. На самом деле можно доказать, что любой алгоритм для вычисления произвольных многочленов будет использовать по крайней мере столько сложений и умножений, сколько схема Горнера, и, таким образом, схема Горнера является оптимальным алгоритмом для вычисления многочленов. Это было доказано (для числа сложений) А. М. Островским в статье 1954 года, которая по существу заложила основы современной науки об оптимальных алгоритмах. Аналогичное утверждение для числа умножений доказал В. Я. Пан в 1966 году. Книга Бородина и Мунро (Borodin and Munro 1975) дает обзор этих результатов, а также других достижений в области оптимальных алгоритмов.

(define (horner-eval x coefficient-sequence)

(accumulate (lambda (this-coeff higher-terms) (??})

0

coefficient-sequence))

Например, чтобы вычислить 1 + 3x + 5x3 + x5 в точке x = 2, нужно ввести (horner-eval 2 (list 1 3 0 5 0 1))

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

Переопределите count-leaves из раздела 2.2.2 в виде накопления:

(define (count-leaves t)

(accumulate (??} (??} (map (??} (??})))

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

Процедура accumulate-n подобна accumulate, только свой третий аргумент она воспринимает как последовательность последовательностей, причем предполагается, что все они содержат одинаковое количество элементов. Она применяет указанную процедуру накопления ко всем первым элементам последовательностей, вторым элементам последовательностей и так далее, и возвращает последовательность результатов. Например, если s есть последовательность, состоящая из четырех последовательностей, ((1 2 3) (4 5 6) (7 8 9) (10 11 12)),то значением (accumulate-n + 0 s) будет последовательность (22 26 30) . Заполните пробелы в следующем определении accumulate-n:

(define (accumulate-n op init seqs) (if (null? (car seqs))

nil

(cons (accumulate op init (??})

(accumulate-n op init (??}))))

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

Предположим, что мы представляем векторы v = (vt) как последовательности чисел, а матрицы m = (mtj) как последовательности векторов (рядов матрицы). Например, матрица

1 2 3 4 "

4 5 6 6 6 7 8 9

представляется в виде последовательности ((1 2 3 4) (4 5 6 6) (6 7 8 9)) . Имея такое представление, мы можем использовать операции над последовательностями, чтобы кратко выразить основные действия над матрицами и векторами. Эти операции (описанные в любой книге по матричной алгебре) следующие:

Скалярное произведение (dot-product v w) возвращает сумму tvtwt; Произведение матрицы и вектора (matrix-*-vector m v) возвращает вектор t, где ti = J2 j mtj v;;

Произведение матриц (matrix-*-matrix m n) возвращает матрицу p, где

Транспозиция (transpose m) возвращает матрицу n, где ntj = mjt

Скалярное произведение мы можем определить так:17

17Это определение использует расширенную версию map, описанную в сноске 12.