Бесплатный курс по Racket. Зарегистрируйтесь для отслеживания прогресса →

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)) ; '()
Упражнение не проходит проверку — что делать? 😶

Если вы зашли в тупик, то самое время задать вопрос в «Обсуждениях». Как правильно задать вопрос:

  • Обязательно приложите вывод тестов, без него практически невозможно понять что не так, даже если вы покажете свой код. Программисты плохо исполняют код в голове, но по полученной ошибке почти всегда понятно, куда смотреть.
В моей среде код работает, а здесь нет 🤨

Тесты устроены таким образом, что они проверяют решение разными способами и на разных данных. Часто решение работает с одними входными данными, но не работает с другими. Чтобы разобраться с этим моментом, изучите вкладку «Тесты» и внимательно посмотрите на вывод ошибок, в котором есть подсказки.

Мой код отличается от решения учителя 🤔

Это нормально 🙆, в программировании одну задачу можно выполнить множеством способов. Если ваш код прошел проверку, то он соответствует условиям задачи.

В редких случаях бывает, что решение подогнано под тесты, но это видно сразу.

Прочитал урок — ничего не понятно 🙄

Создавать обучающие материалы, понятные для всех без исключения, довольно сложно. Мы очень стараемся, но всегда есть что улучшать. Если вы встретили материал, который вам непонятен, опишите проблему в «Обсуждениях». Идеально, если вы сформулируете непонятные моменты в виде вопросов. Обычно нам нужно несколько дней для внесения правок.

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


Нашли ошибку? Есть что добавить? Пулреквесты приветствуются https://github.com/hexlet-basics
Если вы столкнулись с трудностями и не знаете, что делать, задайте вопрос в нашем большом и дружном сообществе