Ленивые последовательности: range, iterate, lazy-seq и чанки

Главная мысль урока: map, filter и их соседи ничего не считают в момент вызова. Они возвращают обещание посчитать, когда спросят. Это даёт бесконечные последовательности и экономию, но ломает код, который ждёт от map побочного эффекта.

В «Хрониках Пограничья» есть подземелье без дна. Этажи не хранятся в файле: игра строит следующий, когда герой спускается по лестнице. Строить все этажи заранее невозможно, их бесконечно много. Строить по одному, когда понадобился, легко.

Clojure умеет так же обращаться с данными. Посмотри, сколько раз сработает функция внутри map:

Атом seen здесь служит счётчиком вызовов, про атомы будет отдельный урок. После def счётчик стоит на нуле: map не вызвал функцию ни разу. Функция сработала, только когда vec попросил элементы. Такой результат называется ленивой последовательностью: она хранит рецепт, а не готовые элементы. Вычисление элементов по запросу называют реализацией.

Бесконечность без зависания

Раз элементы считаются по запросу, последовательность может не иметь конца. Четыре генератора из clojure.core дают бесконечные последовательности:

Функция	Что даёт	Пример начала
(range)	0, 1, 2, …	номера этажей
(iterate f x)	x, (f x), (f (f x)), …	пороги опыта
(repeat x)	x, x, x, …	один и тот же монстр
(cycle coll)	элементы coll по кругу	смена дня и ночи

Каждая строка начинается с take или nth, и это не случайность. Бесконечную последовательность можно преобразовывать (filter в пятой строке работает поверх бесконечной iterate), но печатать, считать count или класть в вектор целиком нельзя: программа будет строить этажи вечно. В браузерной песочнице такой сниппет упрётся в лимит времени, на сервере съест память. Правило: у бесконечной последовательности всегда есть ограничитель, take, take-while, nth или first.

Свой генератор через lazy-seq

Генераторов из таблицы хватает часто, но не всегда. Подземелье строится по своим правилам, и для этого есть макрос lazy-seq. Он откладывает своё тело до первого обращения:

Запусти и посмотри на вывод. def ничего не напечатал. Первый first построил первый этаж, второй first не построил ничего: значение уже запомнено. doall достроил второй и третий этажи, а первый взял готовым.

Обрати внимание на рекурсию. floors-from вызывает саму себя без всякого условия выхода, и это не бесконечный цикл: вызов спрятан внутри lazy-seq и случится, только когда кто-то попросит следующий элемент. Каждый lazy-seq это маленький thunk: отложенное вычисление, которое выполнится один раз. Если хочешь глубже про ленивые стратегии вычисления, загляни в урок о ленивых вычислениях в CS, а в уроке про Haskell лень устроена по умолчанию для всего языка, не только для последовательностей.

Чанки по 32

Теперь странность. Возьмём сто этажей через range и попросим один:

Просили один элемент, функция сработала 32 раза. Это чанк: последовательности поверх range реализуются блоками по 32 элемента, на JVM так же устроены векторы. Ленивость по одному элементу стоит дорого, на каждый элемент нужен свой объект-рецепт. Чанк делает один рецепт на 32 элемента, и map по большой коллекции работает в разы быстрее.

Для чистых функций чанки незаметны: посчитали 32 элемента вместо одного, ответ тот же. Заметны они, когда внутри map есть побочный эффект: запрос к серверу, списание золота, печать. Попросил первого монстра, а атаку получили 32.

Здесь браузер и JVM расходятся. В песочнице вектор отдаёт элементы по одному, а на JVM вектор тоже идёт чанками:

(def seen (atom 0))
(def hits (map (fn [m] (swap! seen inc) m) [:goblin :orc :troll]))
(first hits)
(println "вызовов после first:" @seen)
(assert (= 3 @seen))

На JVM first вызвал функцию для всех трёх монстров, в браузере был бы один вызов. Код, который на это полагается, сломается при переезде. Отсюда вывод: не рассчитывай на то, сколько элементов реализует ленивая последовательность.

Где лень кусается

Самая частая ошибка новичка в Clojure выглядит так:

Функция вернула :done и ничего не напечатала. map построил ленивую последовательность, никто её не прочитал, и вызовы println не случились. Коварство в том, что в REPL такой код выглядит рабочим: если map стоит последним, REPL печатает результат и при этом реализует последовательность. Ты проверил, всё печатается, перенёс код в функцию, и печать пропала.

Когда нужен эффект, а не значение, бери то, что выполняется сразу:

Форма	Что делает	Результат
(doseq [m ms] ...)	цикл ради эффекта	nil
(run! f ms)	вызывает f на каждом элементе	nil
(dorun s)	реализует ленивую последовательность	nil
(doall s)	реализует и возвращает её	сама последовательность
(mapv f ms)	map сразу в вектор	вектор

Вторая ловушка тише. Ленивая последовательность запоминает реализованные элементы, пока на её начало есть ссылка. Если сделать (def events (map parse lines)) над файлом в миллион строк и пройти его до конца, все миллион разобранных событий останутся в памяти: events держит голову. Это называют удержанием головы. Без ссылки на голову пройденные элементы освобождает сборщик мусора, и тот же проход идёт в постоянной памяти. Поэтому длинные потоки данных обрабатывают одним выражением, без промежуточного def, а в уроке про трансдьюсеры увидим, как обойтись вовсе без промежуточных последовательностей.

Попробуй руками

В задаче ты опишешь бесконечное подземелье: пороги опыта через iterate, уровень героя через take-while, размеры волн монстров своим генератором на lazy-seq и объявление о входе в подземелье, которое обязано напечататься, а не застрять в ленивой последовательности.

Проверь себя

Задание

Дальше

Ленивые map и filter это только начало. В следующем уроке соберём всю библиотеку последовательностей: group-by, frequencies, partition, keep и ещё три десятка функций, которыми разбирают лог событий игры без единого цикла.