Трансдьюсеры были анонсированы еще в далеком 2014, с тех пор по ним было написано немалое количество статей (раз, два), но ни после одной статьи я не мог сказать, что понимаю трансдьюсеры кристально ясно. После каждой статьи у меня возникало ощущение, что я приблизительно понимаю что-то сложное, но оно все равно оставалось сложным. А потом однажды в голове что-то щелкнуло: "я ведь уже видел этот паттерн, только он назывался иначе!"
Задача:
Есть массив scores, содержащий результаты проведенных мною игр в футбол в виде объекта с полями:
- gameID — номер игры;
- my — количество очков у меня;
- others — количество очков у моего противника.
Необходимо найти номера первых двух выигранных мною игр.
Исходные данные для задачи (ответ для таких данных — [1, 3]):
const scores = [
{ gameID: 0, my: 1, others: 2 },
{ gameID: 1, my: 2, others: 1 },
{ gameID: 2, my: 0, others: 3 },
{ gameID: 3, my: 3, others: 2 },
{ gameID: 4, my: 3, others: 1 },
{ gameID: 5, my: 0, others: 0 },
{ gameID: 6, my: 4, others: 1 },
]Решение №1. Императивный цикл
Давайте начнем издалека, вернемся в те далекие дни, когда мы писали обычные императивные циклы и мучились изменяемым состоянием (соглашусь, что в данном примере это не вызывает каких-либо проблем):
const result = []
// Пробегаемся по всем играм, пока количество результатов не достигнет двух.
for (let i = 0; i < scores.length && result.length < 2; i++) {
const { gameID, my, others } = scores[i]
if (my > others) {
result.push(gameID)
}
}Тут все довольно просто, красиво и быстро, но императивно и мутабельно. Важно заметить, что лишние итерации не выполняются, цикл завершается сразу после того, как массив с результатами получает нужное количество элементов.
Решение №2. Array#map и Array#filter
Это уже решение иммутабельное, более выразительное, "современное".
const result =
scores
.filter(({ my, others }) => my > others) // выбираем выигрышные
.map(({ gameID }) => gameID) // получаем их номер
.slice(0, 2) // берем первые дваИменно так решило бы большинство js-разработчиков в наши дни, полагаю. Но у этого решения есть одна важная проблема: если в предыдущем решении мы делали всего один проход, да и тот не до конца, то сейчас у нас уже аж два полных прохода. Если бы у нас scores содержал миллион элементов, то предикат в filter вызывался бы миллион раз, функция в map применилась бы меньшее, но все равно большое число раз, а в конце мы все равно берем всего лишь два первых элемента. Конечно, преждевременная оптимизация — зло, но это уже ни в какие ворота.
Решение №3. Свертка
Через свертки можно определить [почти] любую операцию над массивами. В этом решении у нас всего один проход:
const result = scores.reduce((result, { my, others, gameID }) => {
// Если игра выиграна и количество результатов меньше двух,
// то добавляем номер в результаты.
if (my > others && result.length < 2) {
return result.concat([gameID])
}
return result
}, [])Это чем-то напоминает решение с циклами, но тут мы передаем промежуточное состояние явно и иммутабельно. Но проблема осталась — вместо двух проходов у нас теперь один, но он все равно полный, то есть при миллионе элементов мы пройдемся по всему миллиону, даже если нужное число результатов мы уже получили, ведь у стандартного reduce нет возможности выйти из цикла через break. Давайте тогда напишем свой reduce, из которого можно выйти, если вернуть reduced-значение (идею позаимствовал из clojure).
// Класс-обертка для итогового значения аккумулятора.
class Reduced {
constructor(value) {
this.value = value
}
}
const isReduced = value =>
value instanceof Reduced
const reduced = value =>
isReduced(value) ? value : new Reduced(value)
// Рекурсивная реализация reduce с проверкой аккумулятора на reduced-значение.
const reduce = (reducer, state, array) => {
// Если аккумулятор - reduced-контейнер со значением,
// то распаковываем и возвращаем значение, завершая цикл.
if (isReduced(state)) {
return state.value
}
if (array.length === 0) {
return state
}
// Рекурсивно вызовем reduce для хвоста массива,
// применяя первый элемент к состоянию.
const [x, ...xs] = array
return reduce(reducer, reducer(state, x), xs)
}
const result = reduce((result, { my, others, }) => {
if (my > others) {
if (result.length < 2) {
result = result.concat(gameID)
}
// Завершаем цикл, если набрано нужно число результатов.
if (result.length >= 2) {
result = reduced(result)
}
}
return result
}, [], scores)Ух, теперь-то у нас все быстро (один проход и ровно до тех пор, пока мы не получим нужное количество элементов), но красиво ли? Я считаю, что код выше — страшный: в нем слишком много кода, который не относится к задаче.
Решение №4. Декомпозиция редьюсера, трансдьюсеры
Редьюсер выше можно разбить на 4 небольших функции, который будут вызываться по цепочке, где одна функция вызывает следующую.
filterWinsфильтрует игры по статусу, то есть пропускает дальше по цепочке только выигранные игры.mapGameIDдостает из игры ее номер.firstTwoпроверяет количество полученных результатов. Если их меньше двух, то вызывает следующую функцию, получает новые результаты, а потом завершает цикл, если набрано нужное количество.appendToResultдобавляет номер игры в массив с результатами и возвращает его.
// next - следующая функция в цепочке
const filterWins = next => (result, score) =>
// Если игра выигрышная, то передаем ее дальше по цепочке
score.my > score.others
? next(result, score)
: result
const mapGameID = next => (result, { gameID }) =>
// Передаем дальше номер игры
next(result, gameID)
// Эта функция позволяет пропустить через себя ограниченное число элементов.
const firstTwo = next => {
// Мы используем замыкания для добавления локального состояния к нашим редьюсерам.
// n - количество элементов, которые нужно пропустить дальше для добавления в
// массив результатов.
let n = 2
return (result, score) => {
// Если есть свободные места, пропускаем игру дальше и уменьшаем их количество.
if (n > 0) {
result = next(result, score)
n -= 1
}
// Если свободных мест нет, завершаем цикл.
if (n <= 0) {
result = reduced(result)
}
return result
}
}
const appendToResult = (result, gameID) =>
result.concat([gameID])
const result = reduce(
// Последовательно трансформируем редьюсер, применяя наши функции к
// редьюсеру, создавая тем самым цепочку редьюсеров.
filterWins(mapGameID(firstTwo(appendToResult))),
[],
scores,
)Вроде как упростили, разбив на функции, а получилось страшновато. Писать такое каждый раз не очень бы хотелось. Но мы это исправим чуть позже, когда унифицируем код для переиспользования.
Паттерн вам может показаться знакомым, ведь именно так работают middleware. Это и есть middleware. И это и есть трансдьюсеры, потому что трансдьюсеры это и есть middleware. Трансдьюсер — функция, которая принимает один редьюсер и возвращает новый (с дополнительной логикой перед или после вызова редьюсера).
Те, кто слышит понятие middleware впервые, могут ознакомится с ним тут: express.js, laravel, а так же я пробовал вчера объяснить его своими словами: мой пост
В данном решении у нас три трансдьюсера: filterWins, mapGameID и firstTwo, и мы их по последовательно применяем к редьюсеру appendToResult, создавая все более и более сложный редьюсер.
А теперь давайте унифицируем наши трансдьюсеры:
// pred - предикат - функция, которая принимает значение и возвращает true или false.
// Если предикат возвращает true, то пропускаем значение по цепочке дальше, иначе
// возвращаем неизмененный аккумулятор.
const filter = pred => next => (acc, x) =>
pred(x) ? next(acc, x) : acc
// mapper - функция, которая преобразует один элемент в другой.
const map = mapper => next => (acc, x) =>
next(acc, mapper(x))
// Принимает редьюсер и создает новый, который выполнится только n раз.
// После n-ого выполнения цикл завершится.
const take = n => next => (acc, x) => {
if (n > 0) {
acc = next(acc, x)
n -= 1
}
if (n <= 0) {
acc = reduced(acc)
}
return acc
}Заодно переименуем редьюсер:
const append = (xs, x) =>
xs.concat([x])А так же добавим хэлпер для композиции функций, чтобы убрать лишние скобки:
const compose = (...fns) => x =>
fns.reduceRight((x, fn) => fn(x), x)Добавим хэлпер, который применит транcдьюсер к редьюсеру и вызовет reduce с получившимся редьюсером:
const transduce = (transducer, reducer, init, array) =>
reduce(transducer(reducer), init, array)Ну и наконец решим задачу с помощью всех этих функций:
const firstTwoWins = compose(
filter(({ my, others }) => my > others),
map(({ gameID }) => gameID),
take(2),
)
const result = transduce(firstTwoWins, append, [], scores)Получилось красивое, быстрое, функциональное, иммутабельное, готовое к переиспользованию решение.
Вывод:
Трансдьюсеры — очень простой паттерн, который является частным случаем паттерна middleware, который известен намного шире (отсюда и название статьи), основа которого — создание сложных редьюсеров с помощью композиции. А полученные редьюсеры в свою очередь очень универсальны, их можно использовать с обработкой коллекций, стримов, Redux.
Писать весь код для работы с трансдьюсерами каждый раз вручную не придется, ведь трансдьюсеры уже давно реализованы во многих библиотеках для обработки данных (например в ramda.js или стандартной библиотеке clojure)
Ramda:
const scores = [
{ gameID: 0, my: 1, others: 2 },
{ gameID: 1, my: 2, others: 1 },
{ gameID: 2, my: 0, others: 3 },
{ gameID: 3, my: 3, others: 2 },
{ gameID: 4, my: 3, others: 1 },
{ gameID: 5, my: 0, others: 0 },
{ gameID: 6, my: 4, others: 1 },
]
{
const firstTwoWins = compose(
filter(({ my, others }) => my > others),
pluck("gameID"),
take(2),
)
const result = transduce(firstTwoWins, flip(append), [], scores)
}
// Или еще лучше
{
const firstTwoWins = into([], compose(
filter(({ my, others }) => my > others),
pluck("gameID"),
take(2),
))
const result = firstTwoWins(scores)
}Clojure:
(def scores [{:game-id 0, :my 1, :others 2}
{:game-id 1, :my 2, :others 1}
{:game-id 2, :my 0, :others 3}
{:game-id 3, :my 3, :others 2}
{:game-id 4, :my 3, :others 1}
{:game-id 5, :my 0, :others 0}
{:game-id 6, :my 4, :others 1}])
(defn win? [{:keys [my others]}]
(> my others))
(def first-two-wins
(comp (filter win?)
(map :game-id)
(take 2)))
(def result (transduce first-two-wins conj [] scores)) ;; [1 3]Комментарии (84)
elmigranto
01.04.2017 16:47Условие выхода в
forнекорректно, запятая это не && и, если побед в массиве нет, цикл не остановится никогда.
sshikov
01.04.2017 17:03+1Честно говоря, не встречался раньше с таким названием паттерна, как middleware. Возможно, это ограниченнойсть моих познаний, но наверное ссылочка бы не помешала.
kana-desu
01.04.2017 17:34+1Добавил ссылки на описание с документации express.js, laravel, а так же на свое приблизительно объяснение.
sshikov
01.04.2017 17:57+3Я теперь понял, о чем вы. Пожалуй, в классическом понимании, это описание ближе к паттерну chain of responsibility, например.
Просто у термина middleware есть и другое, значительно более широко известное употребление, когда этим словом называют нечно (сервер или сервис), между backend и frontend, базой и web, ну и так далее. И там это не паттерн вообще.kana-desu
01.04.2017 18:30+2Под паттерном я тут понимаю не паттерн проектирования, а просто какой-то повторяющийся кусок кода/повторяющаяся сигнатура. В данном случае под middleware я понимаю что-то вроде обертки, которая принимает функцию и возвращает новую с такой же сигнатурой, но с дополнительной логикой.
sshikov
01.04.2017 21:10+1Да нет, трансдьюсер это вполне себе паттерн проектирования, просто в применении к функциональной парадигме. А в слове middleware меня смущает только то, что у него есть уж очень употребимый и совершенно другой смысл.
>обертки, которая принимает функцию и возвращает новую с такой же сигнатурой, но с дополнительной логикой.
Это просто функция высшего порядка, ничего больше. Как правило — просто композиция. И для этого тоже есть готовая куча терминов, уже, как правило из теории категорий.VolCh
03.04.2017 07:43Это просто функция высшего порядка, ничего больше.
Это один из видов функций высшего порядка. Отличительная от остальных особенностей — принимается параметром функция и возвращается функция с той же сигнатурой, как правило с вызовом параметра внутри.
sshikov
03.04.2017 08:44Ну да, один из видов. На входе редьюсеры (несколько штук), на выходе один редьюсер, результат их композиции. Насчет «той же сигнатуры» я кстати не был бы так уверен.
А то определение, что вы написали — это и есть формулировка термина «функция высшего порядка». Один в один.VolCh
03.04.2017 10:14Функция высшего порядка может принимать на вход функции, а может не принимать, может возвращать функцию, а может не возвращать. Достаточно чего-то одного.
kana-desu
03.04.2017 10:15+1На входе всегда один редьсер. А вот с помощью операции композиции функций (не трандьюсеров) мы можем скомбинировать несколько, но мы можем сделать это и без нее по цеопчке
t3(t2(t1(r)))sshikov
03.04.2017 10:26Хм. Ну да, согласен, теоретически трансдьюсер может принимать один редьюсер, и возвращать другой. Но как правило речь все-таки об их композиции.
redfs
01.04.2017 20:35+2Еще мне нравится, как middleware объясняют на сайте Slim Там очень хорошая схема, сразу все понятно.
Middleware
Horizontal
01.04.2017 18:09+3<zanuda_mode>
Очевидно, что Решение №2 следует записать в виде:
const result = scores .filter(({ my, others }) => my > others) // выбираем выигрышные .slice(0, 2) // берем первые два .map(({ gameID }) => gameID) // получаем их номер
чтобы убрать «лишний» полный проход для получения gameID.
</zanuda_mode>
funca
01.04.2017 18:15+1тут первый проход фильтром по всей коллекции тоже лишний.
kana-desu
01.04.2017 18:28+1А вот можно по-подробнее? Если сделать сперва .slice(0, 2), то мы получим первые две игры независимо от того, выигранные они или нет.
funca
01.04.2017 20:10+1Если в списке 100500 элементов и 2 выигрышных находятся в самом вначале, то неленивый filter все равно пройдет всю коллекцию, прежде чем отдаст результат в map, а тот в slice.
const result = scores .filter(({ my, others }) => my > others) .map(({ gameID }) => gameID) .slice(0, 2)
Если поменять местами map и slice, выигрыш будет. Но это все равно не самый оптимальный вариант. Реализация на базе композиции функций, описанная в статье, переберет лишь необходимое количество элементов.
const result = transduce(compose( filter(({ my, others }) => my > others), map(({ gameID }) => gameID), take(2) ), append, [], scores)
Чисто внешне код отличается не сильно.
kana-desu
01.04.2017 18:27+1Да, так и есть. Я довольно долго работал с ленивыми коллекциями и генераторами, в результате чего привык сначала делать все операции (зачастую над бесконечным списком), а после чего брать нужное количество результатов.
funca
01.04.2017 18:19+2Есть какое-то смутное подозрение, что если эту штуковину (функцию-трансдьсер с аргументом next) вывернуть наизнанку, должен получиться знакомый всем yield, с тем же самым next(), только уже внутри (объекта-генератора) %)
aamonster
01.04.2017 23:12+2Ещё бы. Если переписать это на Хаскеле (ленивость же!) — внезапно окажется, что тут фигурирует единственный тип сущностей: функция, делающая из одного ленивого списка другой. И генераторы — наиболее понятный аналог в некоторых языках...
kana-desu
01.04.2017 23:43Собственно, я переписывал это на хаскеле, но без нормальной реализации take.
Заголовок спойлера
aamonster
02.04.2017 08:52Ужас какой. По моим представлениям — должно быть в точности решение 2.
kana-desu
02.04.2017 09:20+1Из-за ленивости на хаскеле действительно эти трансдьсеры не нужны (если не нужно переиспользовать трансформации) и на js такое действительно можно написать только через генераторы, вы правы.
x |> f = f x main = [1..] |> filter even |> map (* 2) |> take 3 |> print -- [4, 8, 12]
Несколько недель назад я такое тоже писал:
slonopotamus
02.04.2017 01:13+5Теперь вопрос — в чём смысл этого всего? Ну допустим вы героически преодолели функциональщину чтобы она не убивала кхерам производительность, добившись результата идентичного (наверное) изначальному циклу. А ради чего? Увеличение количества уровней абстракции?
HaMI
02.04.2017 01:44Сравните решение 1 и решение 2 – решение 2 и есть «функциональщина» и оно намного более читаемо. При условии, что вы знаете набор очень простых примитивов(.map, .filter, .reduce и производные)
Касательно всех остальных решений – вполне согласем с вашим мнением
kana-desu
02.04.2017 08:56+3Увеличение уровня абстракции в данном случае помогает использовать трансдьюсеры со всеми сворачиваемыми типами (массивы, стримы в rxjs, множества, словари) независимо от того, реализовали ли они функции map/filter/take. Чисто теоретически, если бы трансдьюсеры бы встроили в js, то из всех библиотек типа rxjs/xstream все эти трансформации можно было бы выпилить, оставив только reduce, потому что универсальные трансдьюсеры будут работать однообразно везде.
Nakosika
02.04.2017 13:05+1В смысле зачем map reduce и другие в принципе? Так чтобы эти тупые циклы не писать. Они ведь написаны уже, пора кинуть их на свалку и не писать велосипед в каждом файле по нескольку раз. Плюс целиком эта функциональная конструкция получается более надежной, т. к. количество if/else меньше то меньше вероятность сделать ошибку.
lgorSL
02.04.2017 01:16+1К слову со своей колокольни: в scala можно у коллекций вызвать метод view — вернётся обёртка над коллекцией и операции типа map, filter и т.п. начнут работать лениво.
scores .view // благодаря этой строчке появляется "ленивость" .filter(x => x.my > x.others) // выбираем выигрышные .map(_.gameId) // получаем их номер .take(2) // берем первые два
причём результат — тоже view, "содержащий" 2 элемента и вычисляющий их в самый последний момент.
Возможно, Ваше решение тоже можно так реализовать, чтобы остальной код выглядел по-прежнему.
kana-desu
02.04.2017 08:52+1Да, можно, в js тоже есть библиотеки с ленивыми коллекциями, а в clojure все трансформации по умолчанию ленивы (но при этом ленивые трансформации проигрывают по скорости трансдьюсерам.
Но работа с трансформациями как с объектом первого класса — фишка трансдьюсеров, которая позволяет
а) переиспользовать их
б) использовать одни и те же трансдьсеры для любых типов данных, которые поддерживают свертки (Foldable), скажем, стримы в rxjs (те же самые трансдьюсеры будут прекрасно работать и там), а значит из этих библиотек можно было бы спокойно выпилить все трансформации, если бы трансдьюсеры были бы нативными и общеиспользуемыми (маловероятное будущее, но в clojure стремятся к этому)
Vadem
03.04.2017 13:46На C#, кстати, большинство методов для работы с коллекциями ленивые, так что такой код будет работать «из коробки»:
scores .Where(score => score.my > score.others) .Select(score => score.gameID) .Take(2);
HaMI
02.04.2017 01:16+4Если использовать lodash (а его очень много людей использует), то лишнего прохода не будет благодаря Lazy Evaluation
_(scores) .filter(({ my, others }) => my > others) // выбираем выигрышные .map(({ gameID }) => gameID) // получаем их номер .take(2) .value()
Но главное, ваш пример выглядит так будто вы очень простой(чем проще – тем надежнее) и короткий код (пусть даже не оптимальный, хотя lodash это исправляет) который работает, заменили на какой-то «матан», который в придачу еще и длинее. Зачем?kana-desu
02.04.2017 08:44+5Как я уже сказал, писать все эти трансдьюсеры с нуля не придется. Почти во всех своих проектах я использую ramda (как аналог lodash, только функциональный), который уже имеет реализацию трансдьюсеров (пример в статье есть). Мало того, трансдьюсеры — паттерн намного проще, чем ленивые вычисления (в lodash). Да и и сама ramda намного проще и немагичнее, чем lodash. Так же трансдьюсеры позволяют переиспользовать код, потому что позволяют работать с трансформациями как с объектом первого класса, а потом применять их.
Еще важно то, что трансдьюсеры работают где угодно, где есть reduce, то есть эти трансьдеюсеры будут работать что с lodash, что с ramda, что со стримами (при условии конечно, что они не зависят от реализации reduce, как функция take). Из этого следует вывод, что всякие xstream/rxjs можно было упросить, убрав оттуда filter/map/прочее и оставив только reduce.
Матана в трансдьюсерах нет, в статью я хотел вложить смысл, что это очень простой паттерн, который позволяет добится большой эффективности.
Ну и для сравнения с циклами: читать цепочку трансформация (будь то просто Array#map, или трансдьюсеры) проще, чем циклы с внутренней логикой, так как это декларативно.
HaMI
02.04.2017 12:48Вы не обижайтесь, но начните обосновывать свои утверждения – а то церковь свидетелей Трансдюсера выходит
>паттерн намного проще, чем ленивые вычисления (в lodash)
вас же не просят их имплементировать
>Да и и сама ramda намного проще и немагичнее, чем lodash
ни чем не обоснованое утверждение
>трансдьюсеры работают где угодно
это круто, но зачем? единственное здравое объяснение, которое приходит в голову – тестирование. Но это не проблема
>убрав оттуда filter/map/прочее и оставив только reduce.
я либо что-то не понимаю – либо вы что-то не договариваете.
возьмем простой кусок
const H = require('highland') H(process.stdin) .map(x => 'something' + b) .pipe(process.stdout)
из вашего утверждения выходит что я .map(и любые другие преобразования) могу выразить через .reduce, но ведь .reduce возраващает нам результа когда «пройдет» по всей коллекции – а тут конца коллекции как бы нет.
Я не поленился и проверил:
const H = require('highland') const xf = require('transducers-js').map(H.add('b')); H(process.stdin) .transduce(xf) .pipe(process.stdout)
И что интересно – он работает абсолютно аналогично первому варианту. Я что-то не понимаю про reduce или вы плохо объяснили?
И самое главное: вы так и не объяснили – зачем все это? вы говорите: простой паттерн, который позволяет добится большой эффективности. Обоснуйте это утверждение,
пока что как в вашем примере так и в моем – мы эффективно увеличили количество строк кода и количество зависимостейkana-desu
02.04.2017 14:02+2вас же не просят их имплементировать
они в понимании проще, чем ленивые коллекции, ведь это просто вызов функций по цепочке. Или вы к тому, что не обязательно понимать то, что используешь?
ни чем не обоснованое утверждение
да, это субъективное мнение после чтения исходного кода обеих библиотек
это круто, но зачем? единственное здравое объяснение, которое приходит в голову – тестирование. Но это не проблема
уменьшение повторения кода?
Про последний пункт насчет того, зачем это нужно: трансдьсеры частично решают ту же проблему, что и ленивые коллекции в lodash. Но решение через трансдьюсеры проще хотя бы потому, что тут больше нет довольно сложных ленивых коллекций, нет лишний преобразований с _ и value, нет методов, только функции, и это самый обычный reduce. Вроде как обосновал, нет? (простой паттерн — ведь это просто последовательное выполнение функций, большая эффективность — не выполняются лишние трансформации).
Ramda:
const result = into([], compose( filter(({ my, others }) => my > others), pluck("gameID"), take(2), ), scores)
Lodash:
_(scores) .filter(({ my, others }) => my > others) .map("gameID") .take(2) .value()
Да, обычный цикл конечно проще, но обычный цикл еще и мутабелен, и императивен, ну а (субъективно) читать императивный код сложнее, чем декларативный.
Я мало что знаю про highload, но в xstream свертка вместо возвращения значение при завершении стрим возвращает новый, состоящий из результатов сверток после каждого элемента, то есть
------1-----1--2----1----1------ fold((acc, x) => acc + x, 3) 3-----4-----5--7----8----9------
const map = fn => next => (acc, x) => next(acc, fn(x)) const filter = pred => next => (acc, x) => pred(x) ? next(acc, x) : acc const compose = (f, g) => x => f(g(x)) const append = (arr, x) => arr.concat([x]) const isOdd = x => x % 2 === 1 const inc = x => x + 1 const double = x => x * 2 const xs = xstream.default const button = document.querySelector("button") const clicks$ = xs.create({ start(listener) { button.addEventListener("click", () => listener.next()) }, stop() { button.removeEventListener("click", next) } }).fold(inc, 0) const doubledOdds$ = clicks$.fold(compose( filter(isOdd), map(double), )(append), []) doubledOdds$.addListener({ next(x) { console.log(x) } }) // [2, 6, 10, ...]
Исключетельно чертой трансдьюсеров является то, что они ничего не знают о контексте. Они не знают, как добавлять элемент в конец массива, поэтому вместо этого они делегируют это на оборачиваемый ими редьюсер.
Пока писал это, понял, что я недостаточно компетентен в этой области. Все, что могу сделать — дать ссылку на статью про трансдьюсеры от Рича Хикки — их создателя — https://clojure.org/reference/transducers. Там же есть ссылка на пост в блоге и видео.
SDSWanderer
02.04.2017 02:24+1На правах изврата:
const win = ({ my, others }) => my > others const firstResult = scores.findIndex(win) const secondResult = firstResult + 1 + scores.slice(firstResult + 1).findIndex(win)
В реальном проекте я бы конечно использовал первый или второй вариант.
ticafro
02.04.2017 08:35+1Что скажете про этот вариант?
function archaeological(arr, {filter, map, take}) { let acc = 0, res = [] for (let i = 0; i < arr.length; i++) { if (filter(arr[i])) {acc += 1; res.push(map(arr[i]))} if (take(acc)) return res } } const result = archaeological(scores, { filter({my, others}) {return my > others}, take(x) {return x == 2}, map({gameID, my}) {return {gameID, my}} })kana-desu
02.04.2017 08:36+3Нууу, это выглядит странно
ticafro
02.04.2017 12:10+1в смысле странно? безопасный, легкий вариант для продакшена в 6 строчек кода..)
немного сахарка для вызова функции
const result = archaeological(scores, { filter: ({my, others}) => {return my > others}, take : 2, map : 'gameID' })
dotCypress
02.04.2017 10:11+3Отличная статья, кратко и со смыслом!
Поделюсь своим велосипедом:
Телеграм боты на трансдьюсерах
APXEOLOG
02.04.2017 11:19Немного смутила постановка задачи.
Необходимо найти номера первых двух выигранных мною игр
Я сначала подумал что имеются ввиду первые две игры в хронологическом порядке, а в статье это любые две игры.
Так же смущает наличие поля id у записей, которое намекает на то, что порядок записей в массиве может не совпадать с их хронологическим порядком, что опять же имеет смысл при иной трактовке задачи.
funca
02.04.2017 13:14+1const takeconst take = n => next => (acc, x) => { if (n > 0) { acc = next(acc, x) n -= 1 } if (n <= 0) { acc = reduced(acc) } return acc }kana-desu
02.04.2017 14:13+2Как реализовать пустое перечисление, которое не вернет ни одно элемента?
Нужно просто возвращать acc. reduce требует начальное состояние, именно ого и вернётся для пустого перечисления. При отстуствии начального состояния он берет первый элемент и при пустом массиве Array#reduce кидает исключение.
Должен заметить, что в посте я привел простую реализацию, когда как реально все немного сложнее. Трансдьюсер — это кортеж из трех функций с разным числом аргументов (имена фунцкий образные):
- init — не принимает аргументов и должна вернуть начальное состояние. Зачастую просто вызывает next, то есть делегирует init на следуюущий трансдьюсер.
- step — это то, что в статье — два аргумента: аккумулятор и элемент, возвращает аккумулятор
- result — принимает один аргумент — аккумулятор, срабатывает после завершения reduce.
Кажется такая реализация
takeне композится сама с собой. Если вызватьtake(1)(take(1)), то результат будет обернут в Reduced дважды.Да, это действительно так, спасибо за замечание. Кложурная версия вместо
reducedиспользуетensure-reduced, которая работает как identity, если значение уже обернуто. Исправлю.funca
02.04.2017 19:53`take(0)` это допустимая операция для редьюсера? из реализации следует, что технически вызвать можно, но результат будет такой же как у `take(1)`. т.е. вернется не начальное значение, а результат вызова предыдущей функции. поэтому не понятно баг или фича.
kana-desu
02.04.2017 20:05+1take(0) вернет начальное состояние, потому что не пройдет первая проверка
if (n > 0)и take вернет аккумулятор (а это и есть начальное состояние, если take до этого не выполнялся) вместо отправки аргументов по цепочке дальше.
Другое дело, что все предыдущие редьюсеры выполнятся впустую.
kana-desu
02.04.2017 14:17+1Работать со значением в самом трансдьюсере тоже становится не просто:
Да, это действительно проблема. Но проблема скорее в моей реализации функции reduce, можно попробовать придумать другой способ завершать её выполнение, но у меня идей нет. Можно сделать Reduced каким-нибудь прокси.
Akuma
02.04.2017 22:08-1Вместо пяти строк элементарного цикла, который будет работать очень шустро, вы предлагаете использать prev => next => (a,b,c) => (d,e,f) ад и 100500 строчек кода? :)
На более сложных и однотипных задачах оно может и прокатит. Но на примере из статьи — это маразм :)
Хотя бы укажите в самой статье, что не стоит использать все это чтобы просто выбрать два элемента из массива.kana-desu
02.04.2017 22:25+3а) писать всё это не придется, все это уже реализовано в библиотеках для работы с данными (ramda, clojure.core)
б) использовать императивные циклы я в принципе не считаю хорошей идей, а трансдьюсеры будут намного быстрее, чем .map/.fiter на массивах с большим количеством данных. Ленивые коллекции (как в хаскеле, кложе, lo-dash) или трандьюсеры тут лучший вариант.
Но естественно использовать это для мелких задач поиска по массиву в 10 элементов — оверхед.
nexmean
03.04.2017 08:13использовать императивные циклы я в принципе не считаю хорошей идей
Не завидую я пользователям вашего ПО.
kana-desu
03.04.2017 08:14+3К счастью, на языках, на которых я пишу, циклов в принципе нет (Clojure, для развлечения Elm и Haskell)
nexmean
03.04.2017 10:08-2К счастью на языках, на которых пишите вы, практически никто не пишет ничего серьёзного, а то вызов функции это всё же не очень дёшево, особенно в рамках JS. А если учитывать, что в простенький цикл добавляется ещё 3 бесполезных вызова функций, то всё получается совсем не радужно если масштабировать задачу до сотен тысяч итераций.
Мне, если честно и самому нравятся функциональные решения, но(!) нужно понимать, что твоим кодом в первую очередь будут пользоваться и только во вторую — поддерживать. В связи с этим стоит всё же заменять все эти map(), reduce(), filter() и прочее на циклы во всех случаях, кроме тех, где это серьёзно ударит по читаемости и возможности повторно использовать код. Нет, не везде, но в JS точно.
VolCh
03.04.2017 10:18+1Простенький оптимизатор заинлайнит вызовы функций в цикле. И если функциональные решения улучшают читаемость, то надо ставить их, пока профайлер не скажет, что тормозит или вот-вот начнёт тормозить из-за них.
faiwer
03.04.2017 11:15+1В связи с этим стоит всё же заменять все эти map(), reduce(), filter() и прочее на циклы во всех случаях, кроме тех ...
Может всё-таки строго наоборот? Писать понятный удобный код пока не упрёшься в производительность. А вот уже затем профилирование и оптимизация. И скорее всего там не замена
.mapнаfor ;;будет, а что-нибудь уровня организации кода.
К тому же не стоит забывать, что js это интерпретируемый язык, в котором за кадром происходит очень много "магии", и все эти callback-и легко могут за-inline-иться.
Правда назвать вот такой вот код:
const result = reduce( // Последовательно трансформируем редьюсер, применяя наши функции к // редьюсеру, создавая тем самым цепочку редьюсеров. filterWins(mapGameID(firstTwo(appendToResult))), [], scores, )
Понятным и красивым у меня язык не поворачивается. Та изначальная for-простыня была куда нагляднее:
const result = []; for(const { gameID, my, others } of scores) if(result.length === 2) break; else if(my > others) result.push(gameID);
На мой взгляд JS в текущем виде с текущими тенденциями сильно не хватает
|>-оператора. Все эти композиции функций с оборачиванием всего написанного до этого скобочками изрядно раздражают. Их, в большинстве случаев, ещё и "из глубины" читать надо, а не слева-направо и сверху-вниз.
Касательно производительности. Тут мне кажется стоило бы избегать
return arr.concat(el)иreturn Object.assign(obj, {...})в reducer-ах в пользу мутабельных вариантов, т.к. разница может быть более чем тысячекратной (проверял на object.assign в reduce-цикле). Таки JS пока не Haskell :)faiwer
03.04.2017 11:20Вот небольшой пример про 2600-кратное ускорение. Проверил его на свежей сборке хрома:
mutable: 8.73486328125ms reduce: 19150.360107421875ms
Maiami
03.04.2017 13:46+1Ваш код:
const keys = []; for(let i = 0; i < 100000; i += 10) keys.push(i); console.time('mutable'); const obj1 = {}; for(let key of keys) obj1[key] = key; console.timeEnd('mutable'); console.time('reduce'); const obj2 = keys.reduce((o, key) => Object.assign({}, o, </b> [key]: key }), {}); console.timeEnd('reduce');
Результат:
mutable: 3.034ms reduce: 21646.400ms
Исправленный код, в котором исправлена «опечатка»:
const keys = []; for(let i = 0; i < 100000; i += 10) keys.push(i); console.time('mutable'); const obj1 = {}; for(let key of keys) obj1[key] = key; console.timeEnd('mutable'); console.time('reduce'); const obj2 = keys.reduce((o, key) => Object.assign(o || {}, { [key]: key }), {}); console.timeEnd('reduce');
Результат:
mutable: 3.084ms reduce: 11.763ms
Ускорение всего лишь в 4 раза, поэтому можно не отказываться от Object.assign, если кому-то с ним удобнее/нагляднее.
Почему так получилось?
Вот эта строка:
Object.assign({}, o, { [key]: key })
Исправлена на такую:
Object.assign(o || {}, { [key]: key })
Из документации:
Метод Object.assign() копирует из исходных объектов в целевой объект
Поэтому хоть первый вариант тоже корректный, но он заставляет бесконечно клонировать объект «o» в новый пустой (каждый раз который увеличивается в размерах), вместо того, чтобы просто добавить новый ключ в уже существующий «o».faiwer
03.04.2017 17:15А почему вы решили, что там опечатка? В этом то суть была. Иммутабельность во имя бога иммутабельности. Аналог .concat, но для объектов. Правда я предполагаю, что concat должен быть таки оптимизированным и на деле мутировать объект (либо иметь хитрую структуру, позволяющую ему иметь часть данных общими в разных переменных), пусть хоть и за кадром, а вот с Object.assign такой фокус не прокатил.
Maiami
03.04.2017 17:54Эээ…
Клонировать внутренний объект 10000 раз, только лишь для того, чтобы в результате забрать финальный клон — с трудом верю, что это именно то, что вы хотели сделать.
Именно это и делал ваш код (хотя ваш вариант с for делает другое).
Но если опечатки нет, и это действительно была ваша цель, то что-то вы не то делаете, к производительности js это ни как не относится, и речи про 2600-кратное ускорение тем более не идет.faiwer
03.04.2017 18:16-2с трудом верю, что это именно то, что вы хотели сделать
Я понимаю, но нет, именно это я и хотел сделать. Это был наглядный пример того, что иммутабельность во имя иммутабельности, с полным игнорированием
здравого смыслапринципов работы с памятью, идея изначально обречённая. Такое ещё может прокатить, если язык изначально заточен под такие задачи и имеет под капотом хитроумные оптимизации (аля Haskell).
Примерно также я думаю и про
return arr.concat(el)вreduce-ах. Это выглядит несколько дико, не находите? Но упорно в каждой первой статье проreduceи иже с ним я вижу такие куски кода.Maiami
03.04.2017 18:51+3Вот ваши слова:
Касательно производительности. Тут мне кажется стоило бы избегать return arr.concat(el) и return Object.assign(obj, {...}) в reducer-ах в пользу мутабельных вариантов, т.к. разница может быть более чем тысячекратной (проверял на object.assign в reduce-цикле). ...2600-кратное ускорение.
И вы приводите пример кода, который специально делает много лишней работы (раз вы говорите что это не опечатка).
Потом я привожу исправленный код, и выясняется, что никаких проблем с производительностью нет, Object.assign прекрасно работает в reduce-цикле без потери производительности.kana-desu
03.04.2017 19:16+1Правильный выход — использовать персистентные структуры данных.
faiwer
03.04.2017 19:27-2@kana-desu, Насколько я понимаю, их в JS пока нет. Скажем персистентный hash-map. Да даже set. А на уровне языка их не воссоздать.
sshikov
04.04.2017 20:31+2Э, почему? Ну т.е. я готов поверить, что может получиться медленно и плохо, но по-идее ничего не должно мешать реализации.
kana-desu
05.04.2017 10:28+2Да, скажем, ClojureScript вполне спокойно реализовал всякие персистентные иммутабельные типы типа векторов, списков, хэш-мапов, множеств на js. Все это прогоняется через google closure compiler и реакт-приложения с иммутабельным стейтом на кложовских типах данных работает быстрее, чем react + redux на pure js-объектах.
faiwer
03.04.2017 19:21Моя вина, ок. В процитированной вами цитате я хотел указать
Object.assign({}, obj, т.к. речь вёл про true иммутабельность и ФП, но поторопился. Правда я думал, что это очевидно. Но судя по хейтеру набежавшему на мои комментарии (lol), таки не очевидно. Ок поясню мысль детальнее: в рамках ФП большое значение имеет immutable значения. Reduce в ФП предполагает проброс в него чистой функции. В рамках чистой функцииObject.assign(obj...это грубейшая ошибка. Но в рамках здравого смысла это практически единственный допустимый вариант в циклах приличной длины.Maiami
03.04.2017 19:38Именно поэтому надо избегать Object.assign в reduce, потому что это не тру вэй ФП/чистые_функции, хотя производительность такая же как с вариантом с for-ом?
… так бы я написала, если бы то что вы написали имело смысл.
Какая разница с точки зрения иммутабельности в коде:
Object.assign({}, o, [key]: key }) (медленный вариант)
Object.assign(o || {}, [key]: key }) (быстрый вариант)
Если в обоих случаях «o» это внутренний объект reduce?
Вот ответ:
Код в обоих случаях делает одно и тоже, с одинаковой степенью иммутабельности, никакой разницы нет, только один искусственно тормозной, а второй очень быстрый.
Еще говорят, что у меня женская логика…
ОффтопЯ уже кажется с вами раньше дискутировала и уже приходила к выводу, что это бесполезно.
Наверняка найдется тот, кто поймет ваши хитросплетения мыслей, но у меня на это банально нет желания.faiwer
03.04.2017 19:44-1Какая разница с точки зрения иммутабельности в коде
Разница исключительно в подходе. Баланс между разумностью и фанатичностью. Мы с вами говорим об одном и том же, но разными словами. Даже выводы одни и те же.
Maiami
03.04.2017 19:58+2То есть это не вы рекомендовали не использовать Object.assign, потому что якобы он в тысячи раз медленнее в reduce?
Мы с вами говорим об одном и том же, но разными словами. Даже выводы одни и те же.
Ну да, получается мы об «одном и том же», я привожу данные что падения производительности нет, а вы утверждаете что в 2600 раз медленнее. Ну да, видно что вывод один в один.faiwer
03.04.2017 20:01Maiami, предлагаю продолжить в личку.
Maiami
03.04.2017 20:05Продолжать особо не о чем, потому что я написала изначальный комментарий только чтобы мимо проходящие посетители не ужаснулись вашими псевдо-огромными цифрами и не послушали вашего совета.
Особенно на фоне того, что, как выяснилось позже, вы осмысленно их пытались ввести в заблуждение.
При этом совет про «профилирование» вполне себе разумный.faiwer
03.04.2017 20:22Поясню, я имел, и имею ввиду ровно следующее:
Object.assign({}, o, diffэто медленно, очень медленно. И в цикле так поступать нельзя. Примерно та же ситуация сarr.concat(...items)(но тут допускаю наличие оптимизаций). Отсюда вывод, если возникает желание расширять объект вreduce, то лучше либо мутировать объект напрямую, либо через тот же Object.assign, но задав ему первым аргументом сам объект. Таким образом мы нарушаем принцип иммутабельности, но это разумный компромисс, в особенности, учитывая то, что за пределами цельного вызоваreduceни один объект не модифицируется. Насколько я знаю, примерно также себя ведёт монада St в Haskell. Это совпадает с вашими словами? Да.
Изначально я поторопился и совершил опечатку вот тут, о чём покаялся вот тут. И заодно попытался яснее выразить свою мысль. Но наткнулся лишь на переход личности, пассаж о женской логике и вообще какой-то нездравный напор. Заодно и игнорирование лички. Ну ок, чтож поделать. Это же интернеты.
Если даже после ^ ничего непонятно, то поясню совсем уж тезисно:
Object.assign({},в цикле ? плохоarr.concat(newEl)в цикле, вероятно, тоже плохоObject.assign(el, diff— нормально- точечная мутабельность в функциональном JS — приемлемый компромисс
Maiami
03.04.2017 20:47+2Нельзя просто написать «Не используйте, это медленно, вот цифры показывающие что в 2600 раз медленнее» и надеяться, что все молча это схавают.
Надоело смотреть на то, как никто не хочет отвечать за свои слова «ой, я не то имел ввиду, ой, меня не так поняли, ой я говорил про сферическое фп в вакуме».
faiwer
03.04.2017 17:35-1К слову, в lodash один из моих любимых методов —
_.transform, это примерно то же, что иreduce, но с явным уклоном на мутабельность. Не требуетсяreturn. В таком случае там было бы
.transform((o, key) => { o[key] = key; }, {})
К тому же он поддерживает
break(return false).
TargetSan
02.04.2017 23:29Я честно говоря так и не понял, чем это лучше Iterable, который гораздо понятней и для реализации поддержки в коллекции, и для построения полностью ленивых трансформаций поверх такой ленивой последовательности — в т.ч. reduce.
sshikov
03.04.2017 08:59Iterable слишком расплывчатый термин. Можете пояснить? Тут речь идет не просто о reduce, а о композиции нескольких редьюсеров, разве iterable это про композицию?
TargetSan
03.04.2017 11:33Другими словами, у вас в качестве базовой операции выступает reduce, а также целая обвязка вокруг неё. Чем такой подход лучше простого поэлементного прохода по коллекции как базовой операции? Какие случаи можно (или значительно проще) записать на трансдьюсерах, но нельзя (значительно сложнее) на итераторах? Пока что я вижу, что трансдьюсеры:
- требуют нетривиальную логику во вспомогательном коде
- требуют более нетривиальной работы с пробросом состояния в рекурсивной манере
- применяются к коллекциям точно также через обёртки
Или весь вопрос исключительно в получении функционального иммутабельного ленивого аналога итераторов без ленивых коллекций?
sshikov
03.04.2017 12:07Да, это вот все изначально — про reduce и их композицию.
Все-таки редьюсер это не совсем итератор. Это свертка, и у него в сигнатуре есть элемент коллекции и нечто, куда мы сворачиваем. Т.е. для простоты, текущая сумма, к которой прибавляется очередной элемент. Чем это лучше простого прохода — видимо тем, что это все-таки не совсем простой проход?
Что касается остального, то кратко ответ нет, это не совсем так. Нетривиальной логики там нет никакой, как впрочем и состояния. Его и в reduce нет, вообще говоря. Редьюсер это чистая функция.
Обертки? Тоже скорее нет, чем да. Одна из целей как раз состоит в том, чтобы применять к любому источнику, как скажем коллекции, так и к стриму, т.е. абстрагировать редьюсер (и композицию из них) от источника данных.
>Или весь вопрос исключительно в получении функционального иммутабельного ленивого аналога итераторов без ленивых коллекций?
Вообще на моей памяти трансдьюсеры появились в кложе, и все-таки не совсем для этого. Другое дело что в javascript все может быть иначе.
Собственно, вот оригинальный анонс: http://blog.cognitect.com/blog/2014/8/6/transducers-are-coming
vba
03.04.2017 09:33Ух, теперь-то у нас все быстро (один проход и ровно до тех пор, пока мы не получим нужное количество элементов), но красиво ли?
JS коварен, тут не все так быстро как хотелось бы. Все в одном фор цикле будет пожалуй быстрее.
На мой взгляд трансдьюсеры ака преобразователи как оптимизация, основаны на reduce и если вы понимаете что есть данный оператор и как он работает то вы поймете что такое преобразователь и как он работает.
artemonster
а где шутка?
smallplushbear
"… Вы пишете на этом языке лисп, а потом собственно программу" Грэм кажется.
Или сразу пишите на лиспе. :)