Ленивые и бесконечные последовательности

Понимаем, как Clojure вычисляет последовательности по запросу и работает с бесконечностью.

Ленивая последовательность — последовательность, элементы которой вычисляются не сразу, а по мере того, как их запрашивают.

Что значит «ленивая»

Многие функции (map, filter, range) возвращают не готовый список, а «рецепт» вычисления. Элементы считаются только когда вы реально их читаете. Это экономит память и время: не нужно строить весь результат, если требуется лишь часть.

; range без аргументов задаёт бесконечную последовательность,
; но без запроса ничего не вычисляется
(take 5 (range))        ; => (0 1 2 3 4)
(take 3 (map #(* % %) (range)))  ; => (0 1 4)

Вывод:

(0 1 2 3 4)
(0 1 4)

Бесконечные последовательности

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

; iterate: применять функцию снова и снова
(take 5 (iterate #(* % 2) 1))  ; => (1 2 4 8 16)

; repeat: одно и то же значение
(take 3 (repeat :x))           ; => (:x :x :x)

; cycle: зациклить коллекцию
(take 7 (cycle [1 2 3]))       ; => (1 2 3 1 2 3 1)

Вывод:

(1 2 4 8 16)
(:x :x :x)
(1 2 3 1 2 3 1)

Берём ровно нужную часть

Из бесконечной последовательности берут конечный кусок через take, take-while, first:

; чётные числа: бесконечно, берём первые 4
(take 4 (filter even? (range)))   ; => (0 2 4 6)

; брать, пока выполняется условие
(take-while #(< % 20) (iterate #(* % 2) 1)) ; => (1 2 4 8 16)

Вывод:

(0 2 4 6)
(1 2 4 8 16)

Как работает под капотом

Ленивая последовательность хранит функцию-«мысль», которая при первом обращении вычисляет голову (первый элемент) и хвост (новую ленивую последовательность). Вычисленные элементы кэшируются — повторное чтение не пересчитывает их. Поэтому (range) не зависает: пока вы не попросите элемент, ничего не считается, а take 5 запрашивает ровно пять.

Частые ошибки

• Принудительно вычислить бесконечную последовательность. (count (range)) или печать всей (range) зациклится — всегда ограничивайте через take.
• Думать, что побочные эффекты сработают сразу. Из-за лени map с печатью может ничего не вывести, пока результат не запросят; для эффектов есть doseq/dorun.
• Удерживать голову длинной последовательности. Если хранить ссылку на начало, кэш не освобождается и память растёт.

Итоги

• Ленивые последовательности вычисляют элементы по запросу и кэшируют их.
• Можно описывать бесконечные последовательности: range, iterate, repeat, cycle.
• Конечную часть берут через take, take-while, first.
• Не вычисляйте бесконечную последовательность целиком и помните про отложенность побочных эффектов.