(define fibs (cons-stream 0

(cons-stream l

(add-streams (stream-cdr fibs)

fibs))))

Это определение говорит, что fibs есть поток, начинающийся с 0 и 1, такой, что остаток потока порождается сложением fibs с собой самим, сдвинутым на одну позицию:

112 3 5 8 13 21 ... = (stream-cdr fibs) 0 1123 5 8 13 ... = fibs

0 1 1 2 3 5 8 13 21 34 ... = fibs

Еще одна полезная процедура для подобных определений потоков - scale-stream. Она умножает каждый элемент потока на данную константу:

(define (scale-stream stream factor)

(stream-map (lambda (x) (* x factor)) stream))

Например,

(define double (cons-stream l (scale-stream double 2)))

порождает поток степеней двойки: 1, 2, 4, 8, 16, 32 ...

Можно дать альтернативное определение потока простых чисел, начав с потока целых чисел, и фильтруя его через проверку на простоту. Вначале нам потребуется первое простое число, 2:

(define primes (cons-stream

2

(stream-filter prime? (integers-starting-from 3))))

Это определение не столь тривиально, как кажется, поскольку мы будем проверять число n на простоту, проверяя, делится ли n на простые числа (а не на все целые), меньшие или равные л/п:

(define (prime? n) (define (iter ps)

(cond ((> (square (stream-car ps)) n) true) ((divisible? n (stream-car ps)) false) (else (iter (stream-cdr ps))))) (iter primes))

Это рекурсивное определение, поскольку primes определяются посредством предиката prime?, а он сам использует поток primes. Работает эта процедура потому, что в любой момент имеется достаточно элементов потока primes для проверки на простоту следующего требуемого числа. А именно, при проверке n либо оказывается не простым (а в таком случае имеется уже сгенерированное простое число, на которое оно делится), либо оно простое (а в таком случае,

имеется уже сгенерированное простое число - то есть, простое число меньше п, - большее -\/п.63

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

Не запуская программу, опишите элементы потока, порождаемого (define s (cons-stream 1 (add-streams s s)))

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

Определите процедуру mul-streams, аналогичную add-streams, которая порождает поэлементное произведение двух входных потоков. С помощью нее и потока integers закончите следующее определение потока, n-й элемент которого (начиная с 0) равен факториалу n + 1:

(define factorials (cons-stream 1 (mul-streams (??) (??)))) Упражнение 3.55.

Определите процедуру partial-sums, которая в качестве аргумента берет поток S, а возвращает поток, элементы которого равны S0, S0 + Si, So + Si + S2,.... Например, (partial-sums integers) должно давать поток 1, 3, 6, 10, 15 ...

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

Существует знаменитая задача, впервые сформулированная Р. Хэммингом: породить в возрастающем порядке и без повторений все положительные целые числа, у которых нет других простых делителей, кроме 2, 3 и 5. Очевидное решение состоит в том, чтобы перебирать все натуральные числа по очереди и проверять, есть ли у них простые множители помимо 2, 3 и 5. Однако эта процедура весьма неэффективна, поскольку чем больше числа, тем меньшая их доля соответствует условию. Применим альтернативный подход: назовем искомый поток чисел S и обратим внимание на следующие факты:

•S начинается с 1.

•Элементы (scale-streams 2) также принадлежат S

•То же верно и для (scale-stream S3) и (scale-stream S 5).

•Других элементов S нет.

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

(define (merge s1 s2)

(cond ((stream-null? s1) s2) ((stream-null? s2) s1) (else

(let ((s1car (stream-car s1)) (s2car (stream-car s2))) (cond ((< s1car s2car)

(cons-stream s1car (merge (stream-cdr s1) s2)))

63Это тонкая деталь, которая основана на том, что pn+i < р\ (Здесь pk обозначает k-е простое число.) Такие оценки достаточно трудно доказать. Античное доказательство Евклида показывает, что имеется бесконечное количество простых чисел, и что pn+i < pip2 • • • pn + 1. Никакого существенно лучшего результата не было найдено до 1851 года, когда русский математик П. Л. Че-бышев доказал, что для всех n, pn+i < 2pn. Предположение, что это так, было высказано в 1845 году и известно как гипотеза Бертрана (Bertrands hypothesis). Доказательство можно найти в разделе 22.3 в книге Hardy and Wright 1960.

((> slcar s2car)

(cons-stream s2car (merge sl (stream-cdr s2)))) (else

(cons-stream slcar

(merge (stream-cdr sl)

(stream-cdr s2)))))))))

Тогда требуемый поток можно получить с помощью merge таким образом: (define S (cons-stream 1 (merge (??) (??)))) Заполните пропуски в местах, обозначенных знаком (??).

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

Сколько сложений происходит при вычислении n-го числа Фибоначчи, в случае, когда мы используем определение fibs через процедуру add-streams? Покажите, что число сложений выросло бы экспоненциально, если бы мы реализовали (delay (выражение) ) просто как (lambda () (выражение)), без оптимизации через процедуру memo-proc из раздела 3.5.1.64

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

Дайте интерпретацию потоку, порождаемому следующей процедурой:

(define (expand num den radix) (cons-stream (quotient (* num radix) den)

(expand (remainder (* num radix) den) den radix)))

(Элементарная процедура quotient возвращает целую часть частного двух целых чисел.) Каковы последовательные элементы потока, порожденного выражением (expand 1 7 10) ? Что дает вычисление (expand 3 8 10)?

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

В разделе 2.5.3 мы увидели, как реализовать систему арифметики многочленов, используя представление многочленов в виде списка термов. Подобным же образом можно работать со степенными рядами (power series), например

x2 x3x4

еЛ = 1+Ж + Т + зТ2 + 4ТзТ2+---

24

XX

cos X = 1---1---• • • ,

2 4-3-2

""r 1 3-2 3-L3-2 ••••

представленными в виде бесконечных потоков. Будем представлять последовательность а0 + a\x + a2x2 + a3x3 + • • • как поток, элементами которого являются коэффициенты

a. Интеграл последовательности а0 + а1 x + a2x2 + a3x3 + • • • есть последовательность

1 2 1 3 1 4 c+a0x + -aix +-a2x +-a3x H----2 3 4

64Это упражнение показывает, как близко связан вызов по необходимости с обычной мемоиза-цией, описанной в упражнении 3.27. В этом упражнении мы при помощи присваивания явным образом создавали локальную таблицу. Наша оптимизация с вызовом по необходимости, в сущности, автоматически создает такую же таблицу, сохраняя значения в уже размороженных частях потока.