При всех своих плюсах святая троица map/filter/reduce – в JS не очень экономно работает с памятью. Грандиозный архитектурный костыль – трансдьюсеры – успешно запортирован с Clojure на JS, и поражает неофитов своей непонятностью, при этом вроде как решает проблему с излишним выделением памяти.
При чтении документации на Transducers.js (протокол для трансдьюсеров) меня не оставляло стойкое чувство дежавю – где-то что-то похожее я видел. Ага – итераторы и генераторы на MDN! Все вменяемые браузеры и серверные рантаймы уже их умеют (гусары, молчать про Ишака!).
Не так давно я экспериментировал с этими вещами, чтобы построить нечто, что может потоково обрабатывать данные в JS – без создания промежуточных массивов.
Итак – поехали.
Чтобы было стильно, модно, молодежно – спионерим из интернетов две функции:
const compose = (...fns) => x => fns.reduceRight((c, f) => f(c), x)
Пространные комментарии излишни – классическая композиция функций: compose(f, g, k) это f(g(k(x))). Ух, вроде со скобками не слажал.
И вторая (тут у нас про функциональщину, помним?):
const curry = (fn, a = []) => (...args) =>
a.length + args.length >= fn.length
? fn(...a, ...args)
: curry(fn, [...a, ...args]);
Превращает функцию с кучкой аргументов в функцию одного аргумента. Для условного f(a, b) вызов curry(f) вернет функцию g – обертку для f, которую можно вызвать как g(a, b), так и g(a)(b). Главное, чтобы оборачиваемая функция имела стабильное количество аргументов (никаких аргументов со значениями по умолчанию).
Теперь переизобретем функцию map, используя генераторы.
function *_gmap(f, a) {
for (let i of a) yield f(i);
}
const gmap = curry(_gmap);
Код элементарный, проходимся по входу a функцией f(a) и ответ выкладываем наружу. Можно вызвать как gmap(f, a), так и gmap(f)(a). Что это дает – можно сохранить частично примененный gmap(f) в переменную, а когда понадобится – переиспользовать.
Теперь фильтрация:
function *_gfilter(p, a) {
for (let i of a)
if (p(i)) yield i;
}
const gfilter = curry(_gfilter);
Тоже можно вызвать как сразу – gfilter(f, a), так и в лучших традициях функциональщины – gfilter(f)(a).
Чтоб было проще, еще пара примитивных функций (лиспом навеяло):
function *ghead(a) {
for (let i of a) {
yield i;
break;
}
}
function *gtail(a) {
let flag = false;
for (let i of a) {
if (flag) {
yield i;
} else {
flag = true;
}
}
}
ghead(a) возвращает первый элемент от входа, gtail(a) – всё, кроме первого.
Ну и небольшой пример, как это всё может быть использовано:
let values = [3, 4, 5, 6, 7, 8, 9];
const square = x => x * x;
const squareNfirst = compose(ghead, gmap(square));
let x = [...squareNfirst(values)];
В переменную x попадет массив из одного элемента.
const moreThan5 = gfilter(x => x > 5);
let xxx = [...moreThan5(values)];
Общая идея такая – на вход gmap и gfilter можно скормить как массив, так и нечто, реализующее iterable protocol – а на выходе тоже будет итератор, который в ES6 можно развернуть в обычный массив через три точки ( let x = […squareNfirst(values)] ).
А что же reduce, можете спросить? Универсального подхода тут не будет, или использовать классический [].reduce(f, init), или вот так:
function _greduce(f, i, a) {
let c = i;
for(let v of a) c = f(c, v);
return c;
}
const greduce = curry(_greduce);
greduce(f, i, a) свернет входящий массив или итератор в одно значение.
Пример:
const mixFn = compose(greduce((c, v) => c + v, 0), square, moreThan5);
let yyy = [...mixFn(values)];
Функция-композит последовательно отсечет из входа числа больше 5, потом полученные элементы возведет в квадрат, и напоследок просуммирует с помощью reduce.
Зачем вся эта возня?
Главный профит от того, что обработка на итераторах – в маленьком потреблении памяти. При цепочке преобразований у нас протаскивается один элемент ровно. Плюс если в цепочке преобразований встречаются функции типа ghead(a) – у нас появляется «ленивость», т.е. то, что ghead() не возьмет – даже не будет обсчитываться.
Ну и плюс функциональненько, это сейчас модно :)
Надеюсь, что подобный подход поможет вам сэкономить немножко памяти при обработке много-десятко-мегабайтных массивов. Иначе не стоит и велосипедить.
Комментарии (16)
maxbaluev
02.02.2018 21:22И стоит ли такая экономия, потери понимания кода, особенно сторонними кодерами? Интересно было бы увидеть бенчмарки.
JSmitty Автор
04.02.2018 13:05Как я отметил в конце статьи, это пойдет только если у вас проблемы с потреблением памяти. Это не серебряная пуля. Процессинг данных через map, filter, reduce — декларативный и понятный. Код с compose может быть непривычным, но фактически удобный, гибкий (с for не сравнить), читается легко.
Бенчмарки не делал, самому интересно. Скорее всего сольет вчистую классике на for, на больших объемах должен быть производительнее, чем цепочка методов над array. Может на досуге потестирую, напишу отдельно заметку.
PaulMaly
03.02.2018 00:50Классы в JS — так ли уж необходимы?
punkkk
03.02.2018 14:59А почему, интересно, нет? Никто не навязывает их. Можете использовать, моежете писать на прототипах.
ИМХО, читаемость и структуризация куда удобнее с использованием классов. Да и наследование нагляднее.PaulMaly
03.02.2018 15:46Во-первых, классы это те же прототипы. Всего лишь синтаксис и кстати не самый удобный. Во-вторых, кроме прямого наследования есть и другие способы повторного использования кода.
punkkk
03.02.2018 16:04Поэтому я и не написал, что это «разные вещи». Это приятный сахар. Но на вкус и цвет…
nsinreal
03.02.2018 01:48Нет. Трандьюсеры нужны не только для этого. Они также нужны для того, чтобы полностью разнести логику обработки данных и логику работы с коллекцией. Мне очень жалко, что изначальное обоснование необходимости трандьюсеров просто проходит мимо всех туториалов
1) Изначальный пост о введении transducers в clojure ("Transducers are coming") говорит, что они приходят в «core» и «core.async». К примеру, ваши хваленные итераторы не могут работать с асинхронными источниками данных (rxjs, к примеру). Кейсы, когда нужен реюз одного алгоритма и для массива, и для асинхронного потока — есть, но весьма редки. Если у вас такого нет, то вы можете не использовать трандьюсеры с чистой душой.
2) Трандьюсеры очень серьезно помогают дизайну языка. Рича Хикки просто задолбало то, что для каждого вида коллекции нужно реализовывать набор методов поразительно схожий по коду. Если вы не пишите свой язык и не пишите свои коллекции, то вы можете не обращать внимания на транcдьюcеры с чистой душой. Они просто придут к вам внезапно. Если выживут, конечно.
3) На всякий случай. Изначально в clojure были ленивые последовательности и все методы работы с коллекциями прекрасно с ними работали. Это чтобы вы не думали, что их из-за незнания итераторов ввели.JSmitty Автор
04.02.2018 13:12Спасибо за информативный комментарий. До статьи Рича к стыду своему не добрался, лисп все же мне далек. В обучалках да, нюансы, которые вы описали — потерялись. Моя идея была в том, что экономить память при преобразовании потока можно и более привычным способом.
myrkoxx
Мое ИМХО. Мне только одно не нравиться. Вот есть в проекте боевом код:
Согласитесь, но как по мне читабельность стремится к нулю. Сколько надо времени, чтоб сходу сказать что она делает и как? Особенно радует когда такое надо дебажить, да и еще если что-то где-то упало, и надо отдебажить и сделать хотфикс.
inoyakaigor
Поэтому надо писать комментарии, имярек!
bro-dev
нужно писать такой код который не нуждается в комментировании.
nsinreal
1) А теперь возьмите, и напишите нормальные имена вместо fn, a, args. Потом вынесите условие из тернарника в переменную с говорящим именем. И вообще, разверните тернарник в явный if/else, потому что он сложный.
2) Добавьте JSDoc с пояснением зачем это нужно. Имя curry является стандартом де-факто и облегчает переход между языками программирования, но нарушает концепцию говорящих имен. Так, к примеру C# в свое время говнили за то, что map называется Select, filter называется Where, а reduce называется Aggregate.
3) Обратите внимание на то, что функция curry либо входит в стандартную библиотеку функциональных языков программирования, либо ненужен. Вы не должны видеть такого кода в проекте, потому что этот код должен быть объявлен в какой-то библиотеке.
4) Занимательный прикол: каррирование можно делать и без curry.
Bonart
Ничего, что reduce на самом деле fold?
JSmitty Автор
Как тут заметили — это обычно библиотечная функция. А так я реально нашел в инете реализацию. Код как по мне — не самый очевидный, но при некотором навыке нормально читается. Зависит от того, насколько разработчик "утоп" в функциональном дискурсе. Кстати с ООП та же песня — читать все эти фабрики фабрик фабрик легко с некоторым ооп бэкграундом.