Free Clojure course. Sign Up for tracking progress →

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). Некоторые интерпретаторы и компиляторы могут оптимизировать только рекурсивные вызовы (это уже так называемая оптимизация хвостовой рекурсии), другие — любые хвостовые вызовы.

Instructions

Реализуйте функцию 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)) ; '()
The exercise doesn't pass checking. What to do? 😶

If you've reached a deadlock it's time to ask your question in the «Discussions». How ask a question correctly:

  • Be sure to attach the test output, without it it's almost impossible to figure out what went wrong, even if you show your code. It's complicated for developers to execute code in their heads, but having a mistake before their eyes most probably will be helpful.
In my environment the code works, but not here 🤨

Tests are designed so that they test the solution in different ways and against different data. Often the solution works with one kind of input data but doesn't work with others. Check the «Tests» tab to figure this out, you can find hints at the error output.

My code is different from the teacher's one 🤔

It's fine. 🙆 One task in programming can be solved in many different ways. If your code passed all tests, it complies with the task conditions.

In some rare cases, the solution may be adjusted to the tests, but this can be seen immediately.

I've read the lessons but nothing is clear 🙄

It's hard to make educational materials that will suit everyone. We do our best but there is always something to improve. If you see a material that is not clear to you, describe the problem in “Discussions”. It will be great if you'll write unclear points in the question form. Usually, we need a few days for corrections.

By the way, you can participate in courses improvement. There is a link below to the lessons course code which you can edit right in your browser.

If you got stuck and don't know what to do, you can ask a question in our huge and friendly community