.

Tags:

Searching for a particular element in a JavaScript array is often carried out using a typical iteration. In some cases, forEach and some can be used as well. What is often overlooked is the potential use of Array.prototype.reduce to perform such an operation.

ECMAScript 5.1 specification, in Section 15.4.4.21, describes the callback function to reduce as:

callbackfn is called with four arguments: the previousValue (or value from the previous call to callbackfn), the currentValue (value of the current element), the currentIndex, and the object being traversed.

An illustration of reduce can be seen in the following snippet. Thanks to the addition x + y, the code computes the sum of all numbers in the array, with an optional offset in the second example.

[1, 2, 3, 4, 5].reduce(function (x, y) { return x + y });       //  15
[1, 2, 3, 4, 5].reduce(function (x, y) { return x + y }, 100);  // 115

As a matter of fact, I already covered a rather complicated construct using reduce to produce the Fibonnaci series. To perform a search using reduce, fortunately it does not need to be complicated.

Let’s take a look at the following problem (part of JavaScript Under Pressure): find the longest string in an array of strings. An imperative solution looks something like the following code (using forEach may simplify the loop but the idea remains the same):

function findLongest(entries) {
  for (var i = 0, longest = ''; i < entries.length; ++i) 
    if (entries[i].length > longest.length) longest = entries[i];
  return longest;
}

A version which relies on reduce is a single statement:

function findLongest(entries) {
  return entries.reduce(function (longest, entry) {
    return entry.length > longest.length ? entry : longest;
  }, '');
}
detective

We set the initial value for longest as an empty string. The callback function for reduce ensures that longest will be kept updated because we always choose, via the convenient ternary operator, the longest string for its return value.

Now imagine that the problem is expanded, not only we need to obtain the longest string but we also need to get the index of that longest string in the array. While it sounds more complex, the solution is still as compact as before:

function findLongest(entries) {
  return entries.reduce(function (longest, entry, index) {
    return entry.length > longest.value.length ?
      { index: index, value: entry } : longest;
  }, { index: -1, value: '' });
}

The callback function takes advantage of the third parameter, i.e. the index of the current element. The rest is pretty much the same, except now we need to store a richer object contained both the index and the string, as opposed to just a simple string.

At this point, the problem is made even more challenging: sort the array based on the length of the string. Fortunately, this is again not as crazy as you might think. In fact, we are halfway there since we already have the ability to find the longest string in an array. This is a perfect chance to implement something like insertion sort. For every run, find the longest string, pluck it from our array, and then the push it to the result.

We can realize quickly that the loop needs to run as many as the available array elements. If you read my previous blog post on Sequence with JavaScript Array, it is obvious that we can simply use Array.apply and map for the iteration. The code will look like the following fragment. See if you can figure out the reason behind the use of splice and pop there.

entries = Array.apply(0, Array(entries.length)).map(function () {
  return entries.splice(findLongest(entries).index, 1).pop();
});

Pushing a bit to the extreme, what if the solution can only use reduce? In this case, we need to revive the trick already employed in that Fibonacci series adventure. The use of reduce is reduced (pun intended) to an accumulating iteration, we simply start with an empty array as the initial value and fill this array as we go. Inlining the longest-string-search and shortening a few variables for some additional air of mystery, the complete incantation will be as fascinating as the code below:

entries = Array.apply(0, Array(entries.length)).reduce(function (r) {
  return r.concat(entries.splice(
    entries.reduce(function (longest, e, i) {
      return e.length >= longest.e.length ?  { i: i, e: e } : longest;
    }, { e: '' }).i, 1
  ));
}, []);

Insertion sort is rather impractical in real-world scenarios and the above cascaded construct is not always readable. However, hopefully this can still show that Array.prototype.reduce can be quite charming at times!

  • federicogalassi

    http://www.youtube.com/watch?v=YvR8_owKbNg :)

    A detail specific to “You Can’t Javascript Under Pressure” is that you need to check if the element you get is really a string so it should be:
    return typeof entry == “string” && entry.length > longest.length ? entry : longest;

    • http://ariya.ofilabs.com/ Ariya Hidayat

      The particular detail was intentionally omitted to keep everything simple. And if you want to follow the spirit of the article, just use filter before passing the result to reduce.

      • federicogalassi

        Yes, JUP is about being fast so it makes sense to put everything together, otherwise some .filter(isString).reduce(…) is the definitely right way.

        • http://ariya.ofilabs.com/ Ariya Hidayat

          True, would it lovely as well to see a future version where one can use ECMAScript 6’s array comprehension feature.

  • federicogalassi

    Sorting by plucking a max or min n times is indeed selection sort

  • Frerich Raabe

    I think it’s worth pointing out that `reduce` can be used to express all primitive recursive functions. For instance, `map` could be implemented using `reduce` just like `sum`, `product`, `all` (to test whether all elements in an array satisfy a given predicate), `any` (to test whether any element satisfies a given predicate), `length`, `indexOf` and many more Any time you’re tempted to iterate an entire array by hand, it might make sense to consider `reduce` instead.

    • http://truffles.me.uk Tim Ruffles

      Also it’s my go-to way of doing 2 or more of those functions simulatenously, e.g map + filter:

      xs.reduce(function(all,x) { return test(x) ? all.concat(transform(x)) : all },[])

      • Frerich Raabe

        Yes, this is basically a manual implementation of http://en.wikipedia.org/wiki/Loop_fusion :-/

        It would be nice (as in: more concise and expressive) if one could just write something like

        xs = xs.filter(test).map(transform);

        …and just get a single pass over `xs`, eliding the intermediate array created by the `filter` call completely.

  • Ferdi Ramdhon Nizar

    interesting!

  • adamcbrewer

    I love reading stuff like this to brush-up every now and then. Great post, thanks!

  • adamcbrewer

    I love reading stuff like this to brush-up every now and then. Great post, thanks!

  • Robert Koritnik

    This is a really nice function I never used before. but if user pure for “min/max” search it’s not really fast. I’ve put up a JSPerf test that tests it against usual for loop and Math.max. for loop is the winner here, even though I was expecting more from native reduce function.
    http://jsperf.com/getting-max-value-of-an-array

    • Carl

      Wow, the performance difference is nearly an order of magnitude. `reduce` must just be totally ignored in the under-the-hood implementations, which is a shame — the code as written is much more to the point (and highly readable, if one is familiar with the map-reduce idiom).

      • Robert Koritnik

        I agree. Not too usable in this scenario is it?

      • http://ariya.ofilabs.com/ Ariya Hidayat

        It all depends on the scenario. If my profiling shows that the bottleneck is not on this part of the code, I tend to err on the FP style (also to avoid premature optimization). Also, keep in my mind that JS engines always evolve and the (near) future may look different.

      • kajyr
  • Sylvain Pollet

    What about :
    return entries.slice().sort(“length”)[0];

    • http://ariya.ofilabs.com/ Ariya Hidayat

      It works (for the puzzle). But for the educational purpose of JavaScript functional programming, it misses the point.

  • Dumitru “Mitică” Ungureanu

    What you’re doing is also kind of misses the point of Javascript functional programming.

    I was going to jump on board and say “Nice”, but then it hit me: you’re only returning the _first_ longest string. You need to *filter* the strings array to __all__ the strings with the longest length, not to *fold* it (*reduce* it) it to a single value, in case there are two or more strings with the same longest length.

    And to be honest, I was also mistaken. My solution was to max out the longest string, using underscore.js, oblivious to more than one longest string scenario.

    • http://ariya.ofilabs.com/ Ariya Hidayat

      Getting only one longest string fits the problem definition and in the same spirit as Math.max. It also serves to prepare the stage for the insertion sort example.

      Obviously, there any other edge cases and variants, but those are left as exercises for the reader.

      • Dumitru “Mitică” Ungureanu

        I disagree. There’s something essentially different.

        It’s clearly not about edge cases but about correct or incorrect solutions. The problem is about ‘finding the longest’ not ‘one of the longest’.

        While

        – Math.max applied to [0,1,100,100, 100, 100] results in [100, 100,100,100], which can then be reduced to a single constant, 100;

        – longest length applied to ['a', 'ab', 'lorem ipsum', 'ipsum lorem', 'losum iprem'] on the other hand gives ['lorem ipsum', 'ipsum lorem', 'losum iprem'] and this time even if their length is the same, those can’t be reduced to a same single value.

        • http://ariya.ofilabs.com/ Ariya Hidayat

          The solution presented here is to the problem in that JavaScript Under Pressure puzzle. As far as the puzzle is concerned, the solution is correct.

          • Dumitru “Mitică” Ungureanu

            I disagree again. The puzzle testing cases are lacking.

            The solution you presented and the puzzle tests are in fact all about a corner case: when there is but one longest string.

            From a functional programming point of view the right solution is a __filter__: process a data structure to produce another *data structure*, not a _reduce_: build up a return *value*.

            Personally, I think it should be corrected, both here and on the usvsth3m site. I’ve sent an email to them.

          • http://ariya.ofilabs.com/ Ariya Hidayat

            Personally, I think the given scope is enough to give the meaningful context for the discussion.

  • blunderboy

    This is a nice article indeed. But I don’t understand where should I use this reduce method.
    – Performance wise, it does not gain anything
    – As compared to normal for loop, it makes code less readable.

    • http://ariya.ofilabs.com/ Ariya Hidayat

      Some materials are intentionally not designed for real-world usage, rather as a gate to enrich our knowledge and perspective or even as a stepping stone to study a more in-depth subject.