(define (pairs s t) (cons-stream (list (stream-car s) (stream-car t)) ((как-нибудь смешать) (stream-map (lambda (x) (list (stream-car s) x))

(stream-cdr t)) (pairs (stream-cdr s) (stream-cdr t)))))

Чтобы закончить определение процедуры, нужно выбрать какой-нибудь способ смешать два внутренних потока. В голову приходит воспользоваться потоковым аналогом процедуры append из раздела 2.2.1:

(define (stream-append s1 s2) (if (stream-null? s1)

s2

(cons-stream (stream-car s1)

(stream-append (stream-cdr s1) s2))))

Однако эта идея не срабатывает с бесконечными потоками, поскольку, прежде чем перейти ко второму потоку, нужно пройти весь первый поток до конца. В частности, если мы попробуем породить все пары натуральных чисел при помощи

(pairs integers integers)

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

Для работы с бесконечными потоками требуется придумать способ смешения, который гарантировал бы, что каждый элемент будет достигнут, если программе дать достаточно времени. Изящный способ добиться этого состоит в том, чтобы воспользоваться следующей процедурой interleave:68

(define (interleave s1 s2) (if (stream-null? s1)

s2

(cons-stream (stream-car s1)

(interleave s2 (stream-cdr s1)))))

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

Таким образом, мы можем породить требуемый поток пар так:

(define (pairs s t) (cons-stream (list (stream-car s) (stream-car t)) (interleave

(stream-map (lambda (x) (list (stream-car s) x))

(stream-cdr t)) (pairs (stream-cdr s) (stream-cdr t)))))

68Точная формулировка требования, которому должен удовлетворять порядок слияния, выглядит так: должна существовать функция от двух аргументов f, такая, что пара, соответствующая i-му элементу первого потока и j-му элементу второго, появится в качестве элемента выходного потока под номером f (i, j). Трюк с чередованием через interleave нам показал Дэвид Тёрнер, который использовал его в языке KRC (Turner 1981).

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

Рассмотрим поток (pairs integers integers) Можете ли Вы что-то сказать о порядке, в котором пары попадают в поток? Например, сколько приблизительно пар предшествуют паре (1, 100)? Паре (99, 100)? (100, 100)? (Если Вы способны предоставить точные математические утверждения, - прекрасно. Однако если Вы увязаете в деталях, достаточно качественных оценок.)

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

Измените процедуру так, чтобы (pairs integers integers) порождало поток из всех пар натуральных чисел (i, j), без дополнительного условия i < j. Подсказка: потребуется примешать еще один поток.

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

Хьюго Дум считает, что построение потока пар из трех частей - процедура слишком сложная. Он предлагает вместо того, чтобы отделять пару (So, To), работать с первой строкой целиком:

(define (pairs s t) (interleave

(stream-map (lambda (x) (list (stream-car s) x))

t)

(pairs (stream-cdr s) (stream-cdr t))))

Будет ли такой код работать? Посмотрите, что произойдет, если мы попытаемся вычислить (pairs integers integers) , используя определение Хьюго.

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

Напишите процедуру triples, которая берет три бесконечных потока S, T и U, и порождает поток троек (Si, Tj, Uk), таких, что i < j < k. С помощью triples породите поток всех Пифагоровых троек натуральных чисел, т. е. таких троек (i,j,k), что i < j и i2 + j2 = k2

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

Интересно было бы уметь порождать потоки в каком-либо полезном порядке, а не в порядке, задаваемом к случаю придуманным процессом чередования. Можно воспользоваться методом, подобным процедуре merge из упражнения 3.56, если мы определим способ сказать, что одна пара целых чисел «меньше» другой. Один из способов состоит в том, чтобы определить «функцию взвешивания» Wи постановить, что (i1 ,j1) меньше, чем (i2,j2), если W< W(i2,j2). Напишите процедуру merge-weighted, которая во всем подобна merge, но только в качестве дополнительного аргумента принимает процедуру weight, которая вычисляет вес пары, и используется для определения

69

порядка, в котором элементы должны появляться в получающемся смешанном потоке. При помощи merge-weighted напишите процедуру weighted-pairs, обобщающую pairs. Она должна принимать два потока и процедуру, вычисляющую функцию взвешивания, и порождать поток пар, упорядоченных по весу. Породите, используя эту процедуру:

a.Поток всех пар натуральных чисел (i, j) где i < j, упорядоченных по сумме i + j.

b.поток всех пар натуральных чисел (i, j), где i < j, ни i, ни j не делится ни на 2, ни на 3, ни на 5, и пары упорядочены по значению суммы 2i + 3j + 5ij.

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

Глава 3. Модульность, объекты и состояние initial-value

input

Рис. 3.32: Процедура integral в виде системы преобразования сигналов

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

Числа, которые можно выразить в виде суммы двух кубов более, чем одним способом, иногда называют числами Рамануджана (Ramanujan numbers), в честь математика Шринивасы Рамануджана.70 Упорядоченные потоки пар предлагают изящное решение для задачи порождения таких чисел. Чтобы найти число, которое можно двумя разными способами записать в виде суммы двух кубов, требуется только породить поток пар натуральных чисел (i, j), взвешенных согласно сумме i3 + j3 (см. упражнение 3.70), и искать в этом потоке две пары подряд с одинаковым весом. Напишите процедуру для порождения чисел Рамануджана. Первое такое число 1729. Каковы следующие пять?

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

Используя метод, подобный описанному в упражнении 3.71, породите поток всех чисел, которые можно записать как сумму двух квадратов тремя различными способами (и покажите, каковы эти способы).

Потоки как сигналы

Мы начали обсуждение потоков с того, что описали их как вычислительные аналоги «сигналов» в системах обработки сигналов. На самом деле с помощью потоков такие системы можно моделировать самым непосредственным образом, представляя значения сигнала в последовательные моменты времени как последовательные элементы потока. Например, можно реализовать интегратор (integrator), или сумматор (summer), который, для входного потока x = (xi), начального значения C и малого приращения времени dt, собирает сумму

i

Si = C + Xj dt j=i

и возвращает поток значений S = (Si). Следующая процедура integral напоминает «неявное» определение потока целых (раздел 3.5.2):

(define (integral integrand initial-value dt) (define int

70Цитата из некролога на смерть Рамануджана, написанного Г. Х. Харди (Hardy 1921): «Кажется, это мистер Литлвуд заметил, что «каждое натуральное число было ему другом». Я помню, как однажды навестил его, когда он лежал больной в Путни. Я приехал в такси номер 1729, сказал, что число показалось мне скучным, и выразил надежду, что это не было несчастливым знаком. «Нет, - ответил он, - это очень интересное число; это наименьшее число, которое можно двумя различными способами выразить как сумму двух кубов». Трюк с использованием взвешенных пар для порождения чисел Рамануджана нам показал Чарльз Лейзерсон.