2.2.3 · Конвейеры последовательностей

Конвейер именованных этапов обработки данных

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

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

Как конвейер последовательностей превращает вложенную рекурсию в именованные этапы?

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

enumerate-interval создает исходную последовательность. filter оставляет только значения, принятые odd?, а map заменяет каждое сохраненное значение его квадратом. Каждая процедура отвечает за одно решение.

accumulate объединяет преобразованную последовательность с помощью + и начального значения 0. Полная программа по-прежнему использует рекурсию, но управление распределено по повторно используемым этапам, а не сосредоточено в одной специализированной процедуре.

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

(begin
  (define (enumerate-interval low high)
    (if (> low high)
        '()
        (cons low (enumerate-interval (+ low 1) high))))
  (define (filter predicate items)
    (cond ((null? items) '())
          ((predicate (car items))
           (cons (car items) (filter predicate (cdr items))))
          (else (filter predicate (cdr items)))))
  (define (map procedure items)
    (if (null? items)
        '()
        (cons (procedure (car items))
              (map procedure (cdr items)))))
  (define (accumulate operation initial items)
    (if (null? items)
        initial
        (operation (car items)
                   (accumulate operation initial (cdr items)))))
  (define (square value) (* value value))
  (accumulate + 0
    (map square
      (filter odd? (enumerate-interval 1 8)))))

Примеры

Результат—

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

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

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

Программа возвращает 84 как результат 1² + 3² + 5² + 7².

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

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

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

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

Замените odd? на even?, затем используйте cons и '() вместо + и 0 в accumulate. Предскажите результирующий список и порядок элементов в нем.

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

Финальный этап может принимать любую процедуру с двумя аргументами и подходящее начальное значение.

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

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