Racket: Обход списков и рекурсия

Универсальные функции вроде map и filter — основные инструменты по обработке списков. Но их выразительности хватает не всегда, и тут уже на помощь приходят функции свёртки foldl и foldr. Умение использовать этот готовый инструментарий в теории позволит решать любые задачи, возникающие при работе со списками.

Однако умение работать со списками "вручную" полезно само по себе, так как учит работе с произвольными рекурсивными структурами данных. Вспомните: список — это пара из головы и списка-хвоста, простейшая рекурсивная структура данных!

В функциональном программировании рекурсивные структуры данных принято обрабатывать… рекурсивными функциями! Так, функция, работающая со списком, отделяет голову от хвоста и формирует результат на основе значения головы и результата применения себя к хвосту — сама структура списка диктует то, как с ним нужно работать.

Рассмотрим простейший пример обработки списка на примере функции вычисления суммы его элементов.

Функция будет рекурсивной, а значит нам нужно определиться с условием останова (terminating case) — без него вычисление функции никогда не завершится. Для большинства функций, работающих со списками, останов наступает тогда, когда функция применяется к пустому списку: становится нечего делить на голову и хвост. Вот как функция будет выглядеть в коде:

(define (sum l)
  (if (empty? l)
    0 ; список пустой, сумма равна нулю
    (let ([head (first l)] ; голова
          [tail (rest l)]) ; хвост
      (+ head
         (sum tail))))) ; обрабатываем хвост рекурсивно

Стоит заменить значение для пустого списка на null, а последнее выражение на что-то вроде (cons (f head) (map f tail)), и мы получим свой вариант map! Здесь cons собирает новый список по мере разбора старого. Если образовывать пару по условию, то получится filter! А вот так будут выглядеть функции свёртки (если опустить возможность работы с несколькими списками):

(define (foldr op init l)
  (if (empty? l)
    init
    (let ([head (first l)]
          [tail (rest l)])
      (op head
          (foldr op init tail)))))

(define (foldl op init l)
  (if (empty? l)
    init
    (let ([head (first l)]
          [tail (rest l)])
      (foldl op (op head init)
                tail))))

Хвостовой вызов

Обратите внимание на то, как выглядят рекурсивные вызовы в примере со свёртками:

• (... (foldr ... tail))
• (foldl ... tail)

В первом случае результат вычисления foldr используется для вычисления результата и интерпретатору нужно дождаться результата обработки хвоста.

Во втором же случае сам результат и есть вызов "самое-себя" функции foldl. Результат просто "пробрасывается выше". И тут интерпретатор может упростить себе и вам жизнь! Поскольку дополнительно обрабатывать результат рекурсивного вызова не нужно, можно закончить вычисление текущего вызова функции, заменив вычисление изначального вызова на вычисление рекурсивного. Технически это означает, что интерпретатор не будет увеличивать стек вызовов, а значит появится возможность выполнять рекурсивные вызовы бесконечно долго! Именно поэтому использование foldl предпочтительнее, чем использование foldr, когда обрабатываемые списки достаточно велики.

Умение интерпретатора видеть, когда обычный вызов функции с приращением стека вызовов можно заменить на возврат по стеку выше и подстановку нового вызова, называется оптимизацией хвостового вызова (tail call optimization). Некоторые интерпретаторы и компиляторы могут оптимизировать только рекурсивные вызовы (это уже так называемая оптимизация хвостовой рекурсии), другие (Racket в том числе!) — любые хвостовые вызовы.

Задание

Реализуйте функцию skip, которая должна принимать два аргумента — целое число n и список — и возвращать новый список, содержащий все элементы из первого списка за исключением n первых элементов. Если n окажется больше, чем количество элементов во входном списке, результатом должен быть пустой список.

Примеры:

(skip -5 (list 1 2 3)) ; '(1 2 3)
(skip  0 (list 1 2 3)) ; '(1 2 3)
(skip  1 (list 1 2 3)) ; '(2 3)
(skip 10 (list 1 2 3)) ; '()