Функция reduce

JavaScript в последние годы набрал нешуточную популярность, в связи с чем его подводные камни также стали явственно видны. Справедливости ради, стоит отметить, что любой язык в некоторой мере имеет как своё legacy, так и подводные камни.
Конкретно JavaScript обладает целым огородом камней. Подводным огородом.

На практике, подводные камни встречаются не так часто, напротив, хороший код склонен быть описанным в рамках здорового подмножества языка. Это также является и причиной, почему запомнить все заковырки языка достаточно сложно: они не являются необходимыми для каждодневной практики. Тем не менее, разнообразные граничные случаи использования языковых конструкций это отличная разминка для ума, а также стимул узнать язык немного лучше. Сегодняшний экземпляр попался мне на глаза в процессе прохождения JavaScript Puzzlers.

Меня заинтересовал вопрос номер 3:
Каков результат этого выражения (или нескольких)?

[ [3,2,1].reduce(Math.pow), [].reduce(Math.pow) ]

В качестве ответа авторами, на выбор, даются следующие варианты:
* ошибка
* [9, 0]
* [9, NaN]
* [9, undefined]

Попробуйте и вы, без запуска интерпретатора, пользуясь только своим умом ответить на этот вопрос.

Несмотря на то, что пример достаточно отстранённый, аппликация функций и частично определённых функций к коллекциям это распространённая практика для JS, и, при здравом использовании, она способна сделать код чище, как в плане исполнения — избавить его от лишних замыканий, так и в визуальном плане — меньше скобочного мусора (вопрос использования препроцессоров оставим для другой статьи).

А в этой статье вы найдёте:
* Разбор задачки.
* JavaScript reduce с чисто практической точки зрения.
* Несколько акробатических этюдов с reduce (reduce с академической точки зрения).
* Репозиторий с плюшками к статье.
* Несколько других reduce.

Разбор задачки

Чтож, для начала разберёмся с задачей в начале статьи. А вариантов здесь хватает.
reduce (здесь и далее имеется ввиду Array.prototype.reduce), вместе с другими функциями из прототипа Array: filter, map, forEach, some, every, является функцией высшего порядка, то есть она принимает на вход другую функцию (будем называть эту передаваемую функцию f*). Функция f* будет вызвана с некоторыми агрументами для каждого элемента коллекции.

Конкретно reduce, используется для генерации некоторого агрегирующего значения на основе коллекции. Она последовательно применяет f* к каждому элементу, передавая ей текущее значение переменной, в которой накапливается результат (аккумулятора) и текущий обрабатываемый элемент. Также, в reduce можно передать начальное значение аккумулятора. Причём, (!) поведение reduce будет различаться в зависимости от того, передано это значение или нет.

Функция Math.pow производит возведение в степень, то есть её поведение различается в зависимости от переданной степени: это может быть квадрат, куб, или квадратный корень или любая другая вещественная степень.

При этом остаются открытыми следующие вопросы:
* Как ведёт себя reduce, если вызвать её на пустом массиве?
* Как ведёт себя Math.pow, если недодать ей степень?

Для стандартных функций JS нет общей политики обработки ошибок. Некоторые функции могут действовать строго: бросать исключения, если что-то не так в переданных данных, некоторые будут возвращать всяческие пустые значения: null, undefined, NaN, а прочие будут работать пермиссивно: попытаются что-то сделать даже с не совсем корректными данными.

Как много вопросов затронул всего один пример.

А теперь правильный ответ: мы получим TypeError, в котором виновато второе подвыражение. Функция reduce на пустом массиве И без переданного начального значения бросает TypeError.

Почему так? Вчитываемся в спецификацию reduce

Чтож, давайте почитаем что пишет MDN o Array.prototype.reduce. Выясняются следующие тонкости работы функции:
Если initialValue передано, то на первой итерации функция будет вызвана с этим значением и значением первого элемента массива. Если же, initialValue не передано, то функция будет вызвана со значениями первого и второго элементов массива. Отсюда также следует, что если начальное значение не передано, то функция вызывается на один раз меньше, иначе ровно столько раз, сколько элементов в массиве.

Можно представлять форму с initialValue вот так:

array.reduce(fn, initialValue) ⇔ [ initialValue ].concat(array).reduce(fn);

Вторым интересным аспектом является обработка пустого массива. Если массив пустой, и передано начальное значение, то оно является результатом работы функции, а результат f* игнорируется. Если же массив пуст, а начальное значение не передано, то выбрасывается TypeError.

[].reduce(fn, initialValue) ⇔ [ initialValue ].reduce(fn) ⇒ initialValue;
[].reduce(fn) ⇒ TypeError;

На самом деле поведение функции достаточно логично: она пытается вызвать f* со значениями из входных данных. Если начальное значение передано, то оно является элементом данных идущим перед первым элементом. Если не передано ничего (нет элементов и начального значения), то функция не имеет данных для генерации агрегата, и она выбрасывает исключение. Так или иначе, поведение немножко сложное и может стать подводным камнем. reduce, по сути, перегружается для одного агрумента и для двух, и перегруженные варианты имеют разное поведение на пустом массиве.

Теперь можно понять, почему задачка имеет такой результат, а именно, второе подвыражение бросает исключение: оно вызывается с пустым входным списком и без стартового значения. Но! Первое подвыражение всё-таки вычислилось. Предлагаю в качестве упражнения попытаться разобраться в этом вычислении. Можно пойти двумя путями:
* Джедайский: исполнить код в уме, зная о том как работают reduce и Math.pow.
* Ковбойский: вбить в REPL этот код и попытаться подвести рассуждения под результат.

Также, можно ознакомиться с моим примером, который должен помочь понять задачку:
StreetStrider/habrahabr-javascript-reduce:tests/puzzler.js. Он является jasmine-тестом.

Магия и шарм reduce

reduce примечателен тем, что он может быть использован для того, чтобы описать все остальные функции высшего порядка объекта Array: forEach, filter, map, some, every.

Это станет понятным, если избавиться от мысли, что reduce обязан аккумулировать значение того же типа, что и значения в массиве. Действительно, логичным кажется мыслить, что если мы берём массив чисел и суммируем их, то получаем также число. Если мы берём массив строк и конкатенируем их, то также получаем строку. Это естественно, но reduce также способен возвращать массивы и объекты. Причём передача будет происходить из итерации в итерацию благодаря аккумулятору. Это позволяет строить на reduce функции любой сложности.

Для примера, давайте построим map:

function map$viaReduce (array, fn)
{
	return array.reduce(function (memo, item, index, array)
	{
		return memo.concat([ fn(item, index, array) ]);
	}, []);
};

Здесь через аккумулятор передаётся накапливающийся массив. Он будет того же размера, что и исходный, но со значениями, пропущенными через функцию-трасформатор fn. Также здесь не забыто, то fn принимает не только элемент, но индекс и массив последующими параметрами. Параметр функции concat обёрнут в массив, чтобы избежать «развёртки» значения, если fn вернёт массив. В качестве начального значения передан пустой массив.

Этот код есть в репозитории, а ещё для него есть тесты.

Тем, кто заинтересовался, предлагаю в качестве упражнения реализовать функции filter, и одну из кванторных: some либо every. Вы заметите, что везде используется возврат накапливаемого массива.

Ещё один нетривиальный пример, который приходит на ум, это реализация функции uniq. Как известно, JavaScript страдает от отсутствия в стандартной либе многих нужных вещей. В частности, нет функции, которая устраняет дубликаты в массиве, и разработчики используют разные кастомные реализации (лично я советую использовать _.uniq из LoDash/Underscore).

Эта реализация немного «хипстерская», но как пример возможностей reduce сойдёт.

function uniq$viaReduce (array)
{
	return array.reduce(function (memo, item)
	{
		return (~ memo.indexOf(item) ? null : memo.push(item)), memo;
	}, []);
};

Здесь используется сайд-эффект внутри тернарного оператора, а именно, мы проталкиваем элемент в массив, если он не найден на текущем куске. Оператор тильда используется для сравнения с -1. Всё выражение завёрнуто в оператор запятую, который на каждом шаге (после всех действий) возвращает memo. Примечательно, что эта реализация также сохраняет порядок в массиве.

Код и тесты есть в репозитории.

Ладно, не «немного», этот код был сильно странный, меня оправдывает только наличие тестов и то, что это функция библиотечного типа, поведение которой не будет меняться. Желательно использовать другие реализации в своём коде, использование же как reduce, так и indexOf скажется отрицательным образом на производительности такого uniq, а обильное использование однострочников и тильд — на читаемости.

В качестве разминки, я рекомендую реализовать, например, функцию zipObject суть её в том, что она принимает на вход массив пар (массивов), где нулевой элемент это ключ, а первый — значение, и возвращает сконструированный Object с соответствующими ключами/значениями.

Подробнее о репозитории.

Репозиторий с примерами является npm-пакетом. Его можно поставить, используя адрес на гитхабе:

npm install StreetStrider/habrahabr-javascript-reduce

В src/ лежат примеры функций, в tests/ — jasmine-тесты. Прогнать все тесты можно с помощью npm test.

В репозитории есть также ответ на вопрос о значении Math.pow при отсутствии степени (и другие граничные случаи).

Другие reduce

* В JavaScript у reduce есть злой брат-близнец правосторонний аналог: reduceRight. Он нужен, чтобы агрегировать массивы справа-налево, без необходимости в дорогостоящем reverse.
* LoDash/Underscore есть _.reduce, _.reduceRight. Они обладают рядом дополнительных возможностей.
* В Python есть reduce. Да. Но он официально не рекомендуется к использованию и его даже убрали из глобального неймспейса. Вместо него предлагается использовать списковые выражения и конструкции for-in. Кода получается больше, но он становится намного более читаемым. Это соответствует Дао языка.
* В некоторых языках reduce/reduceRight называются foldl/foldr.

В SQL есть пять стандартных агрегирующих функций: COUNT, SUM, AVG, MAX, MIN. Эти функции используются, чтобы свести результирующую выборку к одному кортежу. Аналогичные функции можно реализовать на JavaScript (тоже на reduce).

Кстати, четыре из пяти агрегирующих функций SQL (не считая COUNT) возвращают NULL, если выборка пустая (COUNT возвращает определённое значение: 0). Это полностью аналогично JS-ному TypeError на пустом списке.

postgres=# SELECT SUM(x) FROM (VALUES (1), (2), (3)) AS R(x);
 sum 
-----
   6
(1 row)

postgres=# SELECT SUM(x) IS NULL AS sum FROM (VALUES (1), (2), (3)) AS R(x) WHERE FALSE;
 sum 
-----
 t
(1 row)

Итог

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

Ссылки

1. JavaScript Puzzlers.
2. MDN: Array.prototype.reduce().
3. github:StreetStrider/habrahabr-javascript-reduce.
4. JavaScript.ru: Массив: Перебирающие методы.

Благодарности

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

Спасибо за внимание.