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

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

Универсальные функции вроде map и filter — основные инструменты по обработке списков. Но их выразительности хватает не всегда, и тут уже на помощь приходят функция свёртки reduce. Умение использовать этот готовый инструментарий в теории позволит решать любые задачи, возникающие при работе со списками.
Однако умение работать со списками "вручную" полезно само по себе, так как учит работе с произвольными рекурсивными структурами данных: вспомните, список это пара из головы и списка-хвоста — простейшая рекурсивная структура данных!
В функциональном программировании рекурсивные структуры данных принято обрабатывать… рекурсивными функциями! Так, функция, работающая со списком, отделяет голову от хвоста и формирует результат на основе значения головы и результата применения себя к хвосту — сама структура списка диктует то, как с ним нужно работать.
Рассмотрим простейший пример обработки списка на примере функции вычисления суммы его элементов.
Функция будет рекурсивной, а значит нам нужно определиться с условием останова (terminating case) — без него вычисление функции никогда не завершится. Для большинства функций, работающих со списками, останов наступает тогда, когда функция применяется к пустому списку: становится нечего делить на голову и хвост. Вот как функция будет выглядеть в коде:

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

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

Так как мы используем рекурсию, вполне возможен вариант с переполнением стека, для предотвращения переполнения используется специальная функция recur (да, интерпретатор Clojure не умеет автоматически оптимизировать рекурсивные вызовы).
Пример:

(defn sum
([vals] (sum vals 0))
([vals acc]
 (if (empty? vals)
   acc
   (recur (rest vals) (+ (first vals) acc)))))
; попробуем вызвать переполнение стека
(sum (vec (range 0 9999999)))
49999985000001
; переполнение стека не произошло!

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

Задание

Реализуйте функцию 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
Если вы столкнулись с трудностями и не знаете, что делать, задайте вопрос в нашем большом и дружном сообществе