(si (stream-ref s 1)) ; Sn (s2 (stream-ref s 2))) ; Sn+1 (cons-stream (- s2 (/ (square (- s2 si))

(+ s0 (* -2 si) s2))) (euler-transform (stream-cdr s)))))

Можно продемонстрировать ускорение Эйлера на нашей последовательности приближений к п:

(display-stream (euler-transform pi-stream))

3.166666666666667

3.1333333333333337

3.1452380952380956

3.13968253968254

3.1427128427128435

3.1408813408813416

3.142071817071818

3.1412548236077655

Более того, можно ускорить ускоренную последовательность, рекурсивно ускорить результат, и так далее. То есть, можно создать поток потоков (структуру, которую мы будем называть табло (tableau)), в котором каждый поток есть результат преобразования предыдущего:

(define (make-tableau transform s) (cons-stream s

(make-tableau transform

(transform s))))

Табло имеет вид

S00 S01 S02 S03 S04 ...

sio sn S12 S13 ...

S20 S21 S22 ...

Наконец, можно построить последовательность, членами которой будут первые элементы каждой строки табло:

(define (accelerated-sequence transform s) (stream-map stream-car

(make-tableau transform s)))

Можно показать, как работает такое «сверхускорение» на последовательности приближений к п:

(display-stream (accelerated-sequence euler-transform

pi-stream))

4.

3.166666666666667

3.142105263157895

3.141599357319005

3.1415927140337785

3.1415926539752927

3.1415926535911765 3.141592653589778

Результат впечатляет. Восемь членов последовательности дают нам верное значение п с точностью до 14 десятичных знаков. Если бы у нас была только исходная последовательность приближений к п, то пришлось бы вычислить порядка 1013 ее элементов (то есть довести последовательность до такого места, где ее элементы становятся меньше 10-13), чтобы добиться такой точности!

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

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

Хьюго Дум спрашивает, почему нельзя было написать sqrt-stream более простым способом, без внутренней переменной guesses:

(define (sqrt-stream x) (cons-stream 1.0

(stream-map (lambda (guess)

(sqrt-improve guess x)) (sqrt-stream x))))

Лиза П. Хакер отвечает, что эта версия процедуры значительно менее эффективна, поскольку производит избыточные вычисления. Объясните Лизин ответ. Сохранилось бы отличие в эффективности, если бы реализация delay использовала только (lambda () (выражение)), без оптимизации через memo-proc (см. раздел 3.5.1)?

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

Напишите процедуру stream-limit, которая в качестве аргумента принимает поток и число (погрешность). Она должна просматривать поток, пока не найдется два элемента подряд, различающихся меньше, чем на погрешность, и возвращать второй из этих элементов. При помощи этой процедуры можно будет вычислять квадратные корни с заданной точностью так:

(define (sqrt x tolerance)

(stream-limit (sqrt-stream x) tolerance))

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

С помощью ряда

ln2 = 1 I + I I + .

2 3 4

породите три последовательности приближений к натуральному логарифму 2, так же, как мы выше сделали это для п. Как быстро сходятся эти последовательности?

Бесконечные потоки пар

В разделе 2.2.3 мы видели, как парадигма работы с последовательностями рассматривает вложенные циклы традиционной парадигмы в виде процессов, определенных на последовательности пар. Если мы обобщим этот метод на

бесконечные потоки, то сможем писать программы, которые трудно воспроизвести с помощью обычных циклов, поскольку «цикл» охватывает бесконечное множество.

Например, пусть нам хочется обобщить процедуру sum-of-primes из раздела 2.2.3 так, чтобы получился поток из всех пар натуральных чисел таких, что i < j и i + j простое. Если int-pairs есть последовательность всех пар натуральных чисел ), где i < j, то необходимый нам поток таков:66

(stream-filter (lambda (pair)

(prime? (+ (car pair) (cadr pair)))) int-pairs)

Задача, следовательно, состоит в том, чтобы породить поток int-pairs. В более общем случае допустим, что у нас есть два потока S = (Si) и T = (Tj), и представим себе бесконечную матрицу

(S0 , Ti) (S0 , T1) (S0, T2) ... (S1 ,T0) (S1 ,T1) (S1 ,T2) ...

(S2, T0) (S2, T1) (S2, T2) . . .

Нам хочется породить поток, который содержит все пары из этой матрицы, лежащие на диагонали или выше, а именно пары

(S0, T0) (S0, T1) (S0, T2) . . .

(S1, T1) (S1, T2) . . . (S2, T2) . . .

(Если мы возьмем и S, и T равными потоку натуральных чисел, то получим как раз необходимый нам поток int-pairs.)

Назовем общий поток пар (pairs S T), и будем считать, что он состоит из трех частей: пары (S0, T0), остатка пар в первом ряду, и всех остальных пар:67

Заметим, что третья часть этой декомпозиции (пары, не лежащие в первом ряду) суть пары, получаемые (рекурсивно) из (stream-cdr S) и (stream-cdr T). Заметим также, что вторая часть (остаток первого ряда) есть

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

Таким образом, мы можем сформировать наш поток пар так:

66Как и в разделе 2.2.3, мы представляем пару натуральных чисел в виде списка, а не лисповской пары.

67В упражнении 3.68 объясняется, почему мы выбрали именно такую декомпозицию.