(define (dot-product v w)

(accumulate + 0 (map * v w)))

Заполните пропуски в следующих процедурах для вычисления остальных матричных операций. (Процедура accumulate-n описана в упражнении 2.36.)

(define (matrix-*-vector m v) (map {??) m))

(define (transpose mat)

(accumulate-n {??) {??) mat))

(define (matrix-*-matrix m n) (let ((cols (transpose n))) (map {??) m)))

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

Процедупа accumulate известна также как fold-right (правая свертка), поскольку она комбинирует первый элемент последовательности с результатом комбинирования всех элементов справа от него. Существует также процедура fold-left (левая свертка), которая подобна fold-right, но комбинирует элементы в противоположном направлении:

(define (fold-left op initial sequence) (define (iter result rest)

(if (null? rest)

result

(iter (op result (car rest)) (cdr rest)))) (iter initial sequence))

Каковы значения следующих выражений?

(fold-right / 1 (list 12 3))

(fold-left / 1 (list 12 3))

(fold-right list nil (list 1 2 3)) (fold-left list nil (list 1 2 3))

Укажите свойство, которому должна удовлетворять op, чтобы для любой последовательности fold-right и fold-left давали одинаковые результаты.

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

Закончите следующие определения reverse (упражнение 2.18) в терминах процедур fold-right и fold-left из упражнения 2.38.

(define (reverse sequence)

(fold-right (lambda (x y) {??)) nil sequence)) (define (reverse sequence)

(fold-left (lambda (x y) {??)) nil sequence))

Вложенные отображения

Расширив парадигму последовательностей, мы можем включить в нее многие вычисления, которые обычно выражаются с помощью вложенных цик-лов.18 Рассмотрим следующую задачу: пусть дано положительное целое число n; найти все такие упорядоченные пары различных целых чисел i и j, где 1 < j < i < n, что i + j является простым. Например, если n равно 6, то искомые пары следующие:

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

Вот способ породить последовательность пар: для каждого целого i < n перечислить целые числа j < i, и для каждых таких i и j породить пару В терминах операций над последовательностями, мы производим отображение последовательности (enumerate-interval 1 n). Для каждого i из этой последовательности мы производим отображение последовательности (enumerate-interval 1 (- i 1)) . Для каждого j в этой последовательности мы порождаем пару (list i j). Это дает нам последовательность пар для каждого i. Скомбинировав последовательности для всех i (путем накопления через append), получаем необходимую нам последовательность пар.19

(accumulate append

nil

(map (lambda (i)

(map (lambda (j) (list i j))

(enumerate-interval 1 (- i 1)))) (enumerate-interval 1 n)))

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

(define (flatmap proc seq)

(accumulate append nil (map proc seq)))

Теперь нужно отфильтровать эту последовательность пар, чтобы найти те из них, где сумма является простым числом. Предикат фильтра вызывается для каждой пары в последовательности; его аргументом является пара и он должен обращаться к элементам пары. Таким образом, предикат, который мы применяем к каждому элементу пары, таков:

18Этот подход к вложенным отображениям нам показал Дэвид Тёрнер, чьи языки KRC и Миранда обладают изящным формализмом для работы с такими конструкциями. Примеры из этого раздела (см. также упражнение 2.42) адаптированы из Turner 1981. В разделе 3.5.3 мы увидим, как этот подход можно обобщить на бесконечные последовательности.

19Здесь мы представляем пару в виде списка из двух элементов, а не в виде лисповской пары. Иначе говоря, «пара» представляется как (list i j), а не как (cons i j).

(define (prime-sum? pair)

(prime? (+ (car pair) (cadr pair))))

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

(define (make-pair-sum pair)

(list (car pair) (cadr pair) (+ (car pair) (cadr pair))))

Сочетание всех этих шагов дает нам процедуру целиком:

(define (prime-sum-pairs n) (map make-pair-sum

(filter prime-sum? (flatmap (lambda (i)

(map (lambda (j) (list i j))

(enumerate-interval 1 (- i 1)))) (enumerate-interval 1 n)))))

Вложенные отображения полезны не только для таких последовательностей, которые перечисляют интервалы. Допустим, нам нужно перечислить все перестановки множества S, то есть все способы упорядочить это множество. Например, перестановки множества {1,2,3} - это {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2} и {3,2,1}. Вот план того, как можно породить все перестановки S: Для каждого элемента x из S, нужно рекурсивно породить все множество перестановок S - x,20 затем добавить x к началу каждой из них. Для каждого x из S это дает множество всех перестановок S, которые начинаются с x. Комбинация всех последовательностей для всех x дает нам все перестановки

S:21

(define (permutations s)

(if (null? s); пустое множество?

(list nil); последовательность,

; содержащая пустое множество

(flatmap (lambda (x)

(map (lambda (p) (cons x p))

(permutations (remove x s))))

s)))

Заметим, что такая стратегия сводит задачу порождения перестановок S к задаче порождения перестановок для множества, которое меньше, чем S. В граничном случае мы добираемся до пустого списка, который представляет множество, не содержащее элементов. Для этого множества мы порождаем (list nil), которое является последовательностью из одного члена, а именно множества без элементов. Процедура remove, которую мы используем внутри permutations, возвращает все элементы исходной последовательности, за исключением данного. Ее можно выразить как простой фильтр:

20Множество S - x есть множество, состоящее из всех элементов S, кроме x.

21 Точки с запятой в коде на Scheme начинают комментарии (comments). Весь текст, начиная от точки с запятой и заканчивая концом строки, интерпретатор игнорирует. В этой книге мы мало используем комментарии; мы стараемся, чтобы программы документировали себя сами при помощи описательных имен переменных.