Reduce function

JavaScript in recent years has gained serious popularity, and therefore its pitfalls have also become clearly visible. In fairness, it is worth noting that any language to some extent has both its own legacy and pitfalls.
Specifically, JavaScript has a whole garden of stones. Underwater garden.

In practice, pitfalls are not as common, on the contrary, good code tends to be described within a healthy subset of the language. This is also the reason why it is rather difficult to remember all the tricks of the language: they are not necessary for everyday practice. Nevertheless, a variety of boundary use cases of language constructs is a great workout for the mind, and also an incentive to learn a language a little better. Today's copy caught my eye in the process of passing JavaScript Puzzlers .

I was interested in question number 3 :
What is the result of this expression (or several)?
')

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

As an answer, the authors give the following options to choose from:
* mistake
* [9, 0]
* [9, NaN]
* [9, undefined]

Try also you, without starting the interpreter, using only your mind to answer this question.

Despite the fact that the example is rather aloof, the application of functions and partially defined functions to collections is a common practice for JS, and, with sound use, it can make the code cleaner, both in terms of performance - to save it from unnecessary closures, and visually The plan is less than staple garbage (the question of using preprocessors is left for another article).

And in this article you will find:
* Parsing the problem.
* JavaScript reduce from a purely practical point of view.
* Several acrobatic etudes with reduce (from an academic point of view).
* Repository with buns for the article.
* Several other reduce .

Analysis of the problem

Well, for a start we will deal with the task at the beginning of the article. And there are plenty of options.
reduce (hereinafter we mean Array.prototype.reduce ), along with other functions from the Array prototype: filter , map , forEach , some , every , is a higher order function, that is, it accepts another function as input (we will call this transmitted f* ) function. The f* function will be called with some arguments for each element of the collection.

Specifically, reduce , used to generate some aggregate value based on the collection. It consistently applies f* to each element, passing it the current value of the variable in which the result (of the accumulator) and the current element being accumulated are accumulated. Also, in reduce you can pass the initial value of the battery. Moreover, (!) The behavior of reduce will differ depending on whether this value is passed or not .

The function Math.pow produces exponentiation, that is, its behavior varies depending on the degree transferred : it can be a square, a cube, or a square root, or any other real degree.

At the same time, the following questions remain open:
* How does reduce behave if called on an empty array?
* How does Math.pow behave if the degree is not Math.pow ?

There is no common error handling policy for standard JS functions. Some functions can act strictly: throw exceptions, if something is wrong in the transferred data, some will return all sorts of null values: null , undefined , NaN , and others will work permissively: they will try to do something even with not quite correct data.

How many questions raised just one example.

And now the correct answer: we get a TypeError that is responsible for the second subexpression. The reduce function on an empty array And without a passed initial value throws a TypeError .

Why is that? Read into the reduce specification

Well, let's read what MDN o Array.prototype.reduce writes . The following subtleties of the function are clarified:
If initialValue passed, then at the first iteration the function will be called with this value and the value of the first element of the array. If, however, initialValue not passed, then the function will be called with the values ​​of the first and second elements of the array. It also follows that if the initial value is not passed, the function is called at one time less , otherwise it is exactly as many times as there are elements in the array.

You can represent the form with the initialValue like this:

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

The second interesting aspect is the handling of an empty array. If the array is empty and the initial value is passed, then it is the result of the function, and the result of f* ignored . If the array is empty and the initial value is not passed, then TypeError thrown.

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

In fact, the behavior of the function is quite logical: it tries to call f* with values ​​from the input data. If the initial value is passed, then it is the data element that precedes the first element. If nothing is transmitted (there are no elements and no initial value), then the function has no data to generate the aggregate, and it throws an exception. Anyway, the behavior is a bit complicated and can become a pitfall. reduce , in fact, is overloaded for one argument and for two, and overloaded options have different behavior on an empty array.

Now we can understand why the problem has such a result, namely, the second subexpression throws an exception: it is called with an empty input list and without a starting value. But! The first subexpression is still calculated. I propose as an exercise try to understand this calculation. You can go two ways:
* Jedi: execute the code in the mind, knowing how reduce and Math.pow .
* Cowboy: drive this code into the REPL and try to reason the result.

You can also familiarize yourself with my example, which should help to understand the puzzle:
StreetStrider / habrahabr-javascript-reduce: tests / puzzler.js . He is a jasmine-test.

Magic and charm reduce

reduce is remarkable in that it can be used to describe all other higher-order functions of an Array object: forEach , filter , map , some , every .

This will become clear if you get rid of the idea that reduce must accumulate a value of the same type as the values ​​in the array. Indeed, it seems logical to think that if we take an array of numbers and sum them, we also get a number. If we take an array of strings and concatenate them, we also get a string. This is natural, but reduce also capable of returning arrays and objects. Moreover, the transfer will occur from iteration to iteration due to the battery. This allows you to build on reduce functions of any complexity.

For example, let's build a map :

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

Here, the accumulating array is transmitted through the battery. It will be the same size as the original, but with values ​​passed through the function-transformer fn . Also not forgotten here, fn accepts not only an element, but an index and an array with subsequent parameters. The parameter of the function concat wrapped in an array to avoid “unwinding” the value if fn returns an array. An empty array is passed as the initial value.

This code is in the repository, and there are also tests for it.

For those who are interested, I propose to implement the filter functions as an exercise, and one of the quantifier functions: some or every . You will notice that the return of the accumulated array is used everywhere.

Another non-trivial example that comes to mind is the implementation of the uniq function. As you know, JavaScript suffers from the lack of many necessary things in the standard lib. In particular, there is no function that eliminates duplicates in the array, and developers use different custom implementations (I personally advise using _.uniq from LoDash / Underscore).

This implementation is a bit “ hipster ”, but as an example of reduce capabilities, it will come down.

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

Here the side effect is used inside the ternary operator, namely, we push an element into the array if it is not found on the current piece. The tilde operator is used to compare with -1 . The whole expression is wrapped in a comma operator, which at each step (after all actions) returns a memo . It is noteworthy that this implementation also maintains order in the array.

The code and tests are in the repository.

Okay, not “a bit”, this code was very strange, I am justified only by the presence of tests and the fact that this is a library type function, whose behavior will not change. It is advisable to use other implementations in your code, but using both reduce and indexOf will have a negative effect on the performance of such uniq , and the abundant use of one-liners and tildes will affect readability.

As a warm-up, I recommend implementing, for example, the zipObject function zipObject essence in that it takes as an input an array of pairs (arrays), where the zero element is the key and the first is the value, and returns the constructed Object with the corresponding keys / values.

Read more about the repository.

The repository with examples is the npm-package. It can be delivered using the address on the githab:

 npm install StreetStrider/habrahabr-javascript-reduce 

In src/ are examples of functions, in tests/ - jasmine-tests. You can run all the tests using npm test .

The repository also contains an answer to the question about the value of Math.pow in the absence of a degree (and other boundary cases).

Other reduce

* In JavaScript, reduce has an evil twin brother, right-hand analog: reduceRight . It is needed to aggregate arrays from right to left, without the need for costly reverse .
* LoDash / Underscore is _.reduce , _.reduceRight . They have a number of additional features.
* Python has a reduce . Yes. But it is not officially recommended for use and it has even been removed from global namespace. Instead, it is proposed to use list expressions and for-in constructions. The code turns out more, but it becomes much more readable. This corresponds to the Tao language.
* In some languages, reduce/reduceRight is called foldl/foldr .

There are five standard aggregate functions in SQL: COUNT , SUM , AVG , MAX , MIN . These functions are used to reduce the resulting sample to a single tuple. Similar functions can be implemented in JavaScript (also on reduce ).

By the way, four of the five SQL aggregation functions (not counting COUNT ) return NULL if the sample is empty ( COUNT returns a specific value: 0 ). This is completely analogous to the JS TypeError on an empty list.

 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) 

Total

reduce is a powerful function in terms of which other higher order functions can be expressed, such as map and filter . With this power, complexity comes to reduce . reduce can be successfully used for various summations and groupings, however, it is worth remembering that any aggregation can be rewritten using a regular loop, which can be easier to read.

Links

1. Javascript puzzlers
2. MDN: Array.prototype.reduce () .
3. github: StreetStrider / habrahabr-javascript-reduce .
4. JavaScript.ru: Array: enumerating methods .

Thanks

Thanks to subzey for pushing me to the idea that reduce can return anything.
Thanks to everyone who will write me a personal error messages and shortcomings in the article, as well as in the repository.

Thanks for attention.