3.5.3 · Применение парадигмы потоков

Потоки частичных сумм и приближений корня

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

Вопрос для размышления

Что меняется, когда численная итерация описывает каждое последовательное приближение вместо сокрытия всех промежуточных шагов ради итогового ответа?

Представление последовательных численных состояний как элементов потока
Накопление бесконечного потока членов в точные частичные суммы
Генерация приближений квадратного корня по методу Ньютона без фиксированного цикла итерации
Запрос конечного префикса с сохранением остального процесса отложенным
Наблюдение за конечной последовательностью улучшений Ньютона

Процедура alternating-terms описывает 1, −1/2, 1/3, −1/4 и так далее. Процедура partial-sums передает накопленную сумму в отложенный хвост, поэтому каждый элемент потока является повторно используемым приближением к бесконечному знаковопеременному гармоническому ряду. Процедура stream-take вычисляет только пять пар, отображаемых в результате.

Поток sqrt-stream раскрывает каждое улучшение Ньютона для √2. Его точная рациональная последовательность начинается с 1, 3/2, 17/12, 577/408 и 665857/470832. Последующие потребители могут исследовать больше приближений без изменения производителя. Отображаемый префикс фиксирует последовательность улучшений для выбранного начального значения.

Код SICP583 из 1,048,576 байт UTF-8

(begin
  (define (stream-take stream count)
    (if (= count 0)
        '()
        (cons (car stream)
              (stream-take
                (force (cdr stream))
                (- count 1)))))
  (define (alternating-terms n sign)
    (cons-stream
      (/ sign n)
      (alternating-terms (+ n 1) (- sign))))
  (define (partial-sums stream total)
    (let ((next-total (+ total (car stream))))
      (cons-stream
        next-total
        (partial-sums
          (force (cdr stream))
          next-total))))
  (stream-take
    (partial-sums (alternating-terms 1 1) 0)
    5))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Частичные суммы равны (1 1/2 5/6 7/12 47/60). Приближения квадратного корня равны (1 3/2 17/12 577/408 665857/470832).

На что обратить внимание в трассе

Считайте операции force вместо представления уже материализованного бесконечного списка. В partial-sums проследите за передачей предыдущей суммы в следующий отложенный шаг. В sqrt-stream отделяйте текущее приближение от формулы, захваченной в promise для следующего приближения.

Попробуйте сами

Измените программу и сравните результат.

Создайте поток частичных сумм обратных квадратов и возьмите шесть значений. Затем напишите потребитель stream-limit, который останавливается, когда два последовательных неточных приближения различаются менее чем на видимый допуск погрешности.

Показать подсказку

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

Завершить этот урок

В этой главе пройдено 0 из 21 урока0%