Трансдьюсеры: преобразование без промежуточных коллекций

Главная мысль урока: (map f) и (filter p) без коллекции это не ленивые последовательности, а преобразования одного шага редукции. Их склеивают через comp и применяют к чему угодно: к вектору, к ленивой последовательности, к каналу. Данные проходят цепочку за один проход, и промежуточных коллекций нет.

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

Читается хорошо. Но посмотри, что происходит внутри. filter строит ленивую последовательность ударов. map строит поверх неё вторую, последовательность чисел. reduce проходит по второй. Для четырёх событий это неважно. Для ста тысяч это две промежуточные последовательности по сто тысяч ячеек, которые сразу выбросит сборщик мусора.

Порядок работы цепочки

На JVM разница видна по порядку вызовов. Цепочка ->> над вектором работает кусками по 32 элемента: сначала map обрабатывает весь кусок, потом filter берётся за результат. Вторая строка делает то же самое трансдьюсером:

(defn spy [tag f] (fn [x] (print (str tag x " ")) (f x)))

(def chain
  (with-out-str
    (->> [1 2 3] (map (spy "m" identity)) (filter (spy "f" odd?)) doall)))

(def xf
  (with-out-str
    (into [] (comp (map (spy "m" identity)) (filter (spy "f" odd?))) [1 2 3])))

(println chain)   ; m1 m2 m3 f1 f2 f3
(println xf)      ; m1 f1 m2 f2 m3 f3
(assert (= "m1 m2 m3 f1 f2 f3 " chain))
(assert (= "m1 f1 m2 f2 m3 f3 " xf))

Цепочка строит слой за слоем: сначала все результаты map, потом все результаты filter. Трансдьюсер проводит каждый элемент через всю цепочку, прежде чем взять следующий. Это и есть один проход.

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

Что такое трансдьюсер

Вспомни reduce. У него есть редуцирующая функция: она берёт накопленное и очередной элемент и возвращает новое накопленное. + такая функция, conj тоже.

Что делает filter в терминах reduce? Пропускает элемент дальше или нет. А map? Заменяет элемент перед тем, как отдать его дальше. Ни тому, ни другому не нужно знать, откуда пришёл элемент и куда он уйдёт. Обоим нужна только следующая редуцирующая функция в цепочке.

Трансдьюсер это функция от редуцирующей функции к редуцирующей функции. Напишем map сами, чтобы увидеть, что внутри:

Три арности это договор трансдьюсера:

1. Без аргументов: вернуть начальное значение, спросив его у следующего шага.
2. С одним аргументом: редукция закончилась, можно дописать хвост.
3. С двумя: обычный шаг.

Наш my-map работает в паре со встроенным filter, потому что оба следуют этому договору. Нигде в коде нет ни вектора, ни последовательности: только шаги.

comp читается слева направо

Склеенный трансдьюсер для боя выглядит так:

Обычный comp применяет функции справа налево: ((comp f g) x) это (f (g x)). С трансдьюсерами порядок выглядит обратным: сначала filter, потом map, как в цепочке ->>. Причина в том, что comp склеивает обёртки над шагом. Внешняя обёртка, filter, получает элемент первой и решает, звать ли внутреннюю.

Один трансдьюсер, разные приёмники

damage-xf ничего не знает о том, что с ним сделают. Его можно применить по-разному:

Функция	Что делает	Результат
(transduce xf f init coll)	сворачивает в одно значение	число, мапа, что вернёт f
(into to xf coll)	собирает в коллекцию	вектор, множество, мапа
(sequence xf coll)	ленивая последовательность	вычисляется по запросу
(eduction xf coll)	рецепт без вычисления	пересчитывается при каждом обходе
(chan n xf)	канал core.async	значения проходят xf по пути

Последняя строка таблицы уже встречалась в уроке про core.async: тот же (keep parse-line) разбирал лог и в векторе, и в pipeline. Источник и приёмник отделены от преобразования, и это главная причина, зачем трансдьюсеры придуманы.

Свой трансдьюсер с состоянием

Некоторым шагам нужна память. dedupe помнит прошлый элемент, partition-all копит группу. Напишем numbered: он пронумерует события боя.

Состояние создаётся внутри (fn [rf] ...), а не снаружи. Эта функция вызывается заново при каждом применении трансдьюсера, поэтому второй into начал счёт с единицы. Если завести volatile! выше, все применения делили бы один счётчик, и второй бой продолжил бы нумерацию первого.

volatile! здесь вместо атома: трансдьюсер работает в одном потоке, и гарантии swap! ему не нужны.

reduced: остановиться раньше

Бывает, что дальше идти не нужно. (take 3) после третьего элемента сообщает редукции: хватит. Делает он это через reduced, обёртку над значением, которую reduce и transduce понимают как «стоп»:

Обе строки работают с бесконечными источниками: (range) и (repeat ...). Без reduced редукция не закончилась бы никогда. Во второй строке reduced вернула редуцирующая функция, но трансдьюсер может вернуть его и сам, как делает take. Этим ты воспользуешься в задаче.

Сравни со схемами рекурсии: там свёртка тоже отделена от структуры, по которой она идёт. Трансдьюсер делает ещё один шаг и отделяет преобразование от самой свёртки.

Когда не нужно

Трансдьюсер не замена ->> во всех случаях. Цепочка на трёх элементах читается проще, и выигрыша от одного прохода там нет. Берут трансдьюсеры, когда:

• данных много, и промежуточные последовательности заметны в профилировщике;
• одно преобразование нужно применить к разным источникам: вектору, файлу, каналу;
• нужен ранний выход или состояние, а писать loop вручную не хочется.

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

В задаче ты соберёшь трансдьюсер ударов, посчитаешь урон и напишешь until-dead: трансдьюсер с состоянием, который ведёт здоровье монстра и останавливает бой на последнем ударе.

Проверь себя

Задание

Дальше

Трансдьюсеры понадобятся в финальном проекте, где весь events.log разбирается за один проход. Перед этим разомнёмся на задачах с собеседований: частоты, обход графа и динамика на структурах Clojure.