.

Tags:

lock

Instead of using loops, JavaScript Array object is quite powerful to create sequences. What about some more complex series and not just a list of consecutive numbers or letters? Fortunately, we still have other Array’s functions such filter, map, every, and reduce at our disposal. Those can be used to generate a list of prime numbers, compute the factorial, and produce the Fibonacci series.

Prime Numbers

Prime numbers are fascinating, in particular because the concept is so simple and yet there are multiple ways dealing with them so that the tasks are often employed in problem-solving interviews. Every JavaScript programmer worth her salt should be able to come up with a simple way to check whether a given integer i is a prime number or not. One possible loop-based solution, for i >= 2, is given as follows:

function isPrime(i) {
  for (var c = 2; c < = Math.sqrt(i); ++c)
    if (i % c === 0) return false;
  return true;
}

The above primality test implementation is probably not the most optimal one, it is enough to illustrate the concept.

From this function, the next task is to print all prime numbers between 0 and N:

function primeList(N) {
  var list = [];
   for (var i = 2; i != N; ++i)
     if (isPrime(i)) list.push(i);
  return list;
}

We already learned that some loop-based iterations can be turned into Array one-liners. Can we apply the same technique to the above problem?

Let us tackle isPrime() first. The suitable solution here is to use Array.prototype.every. In Section 15.4.4.16, the ECMAScript 5.1 specification says:

every calls callbackfn once for each element present in the array, in ascending order, until it finds one where callbackfn returns false. If such an element is found, every immediately returns false. Otherwise, if callbackfn returned true for all elements, every will return true.

In other words, we can use every to check for every potential divisor and see if one of them is the divisor for the candidate. If yes, obviously the candidate is not a prime number and we just need to bail out immediately. If there is a suitable divisor after the exhaustive search, it means we find our prime number.

Surprisingly, the code is shorter that the above explanation. Also, ~~ trick is being used instead of Math.floor, for some additional mystery.

function isPrime(i) {
  return (i > 1) && Array.apply(0, Array(1 + ~~Math.sqrt(i))).
    every(function (x, y) { return (y < 2) || (i % y !== 0) });
}

The other function, primeList(), is rather easy to refactor. Recall again the approach of using the combination of Array constructor, apply, and map, we end up with the following final solution. Note that the primality test is now inlined via the use of Array.prototype.filter.

function primeList(N) {
  return Array.apply(0, Array(N)).map(function (x, y) { return y }).
    filter(function (i) {
      return (i > 1) && Array.apply(0, Array(1 + ~~Math.sqrt(i))).
        every(function (x, y) { return (y < 2) || (i % y !== 0) });
    });
}

The (deadly) combination of map, filter, and every is apparently enough to avoid the loops!

If you care about the upcoming ECMAScript 6, the use of arrow function and array comprehension permits the above construct to be written as:

function primeList(N) {
  return [for (i of Array.apply(0, Array(N)).map((x, y) => y))
    if ((i > 1) && Array.apply(0, Array(1 + ~~Math.sqrt(i))).
      every((x, y) => (y < 2) || (i % y !== 0) ))
    i];
}

Factorial

Computing factorial is another math-related intriguing activity. In fact, due to its nature, this becomes the usual exercise for recursive programming introduction. For now, let us rather focus on the non-recursive implementation, something along the line of:

function factorial(n) {
  var f = 1;
  for (var c = 1; c < = n; ++c) f *= c;
  return f;
}

Here, if we want to avoid the imperative style of using a loop, the strategy will be different. Because computing the factorial of n depends on all the previous values, we can not simply use map or even every like in the previous example. For this, we need the help of Array.prototype.reduce. The specification, in Section 15.4.4.21, has something to say about this higher-order function :

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.

It is likely easier to understand reduce from the following simple illustration:

[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

Because of x + y, the above code essentially produces the sum of every number in the array. Here x corresponds to the previous value and y is the current value (which will go from 1 to 5). In this context, imagine x acts like an accumulator. Note also that reduce can accept an optional second argument which will become the initial value. In the above example, 100, this will offset the computed total.

We can also do things like the following. Not only the array element (current value, y) is being used, the callback also uses the element index, passed as the third argument z.

[14, 3, 77].reduce(function(x, y, z) { return x + y * z }, 0);   // 0*14 + 1*3 + 2*77

If you make it this far, you probably already come up with a solution to the factorial problem. Here is an exemplary implementation. Note the return value from the callback, it is not straightforward because the element index z starts from 0, not from 1.

function factorial(n) {
  return Array.apply(0, Array(n)).reduce(function(x, y, z) { return x + x * z; }, 1);
}

As usual, here is the ECMAScript 6 version with an arrow function:

function factorial(n) {
  return Array.apply(0, Array(n)).reduce((x, y, z) => x + x * z, 1);
}

Finally, for a comparison see also this tweet from Angus Croll (@angustweets). For a different take, check out the version from Jed Schmidt (@jedschmidt) where the function itself is also reused as the callback for reduce.

Fibonacci Series

This short treatise is incomplete without Fibonacci series, often associated with the growth of rabbit population. The idea behind Fibonacci numbers is relatively simple and yet there can be dozens of puzzling programming tasks associated with it.

If one is asked to show the first n Fibonacci numbers, her implementation can look like:

function fibo(n) {
  var f = [];
  for (var c = 0; c < n; ++c) {
    f.push((c < 2) ? c : f[c-1] + f[c-2]);
  }
  return f;
}

If we want to switch the implementation to leverage JavaScript Array object, the situation with the two previous values becomes a real problem. Relying on reduce would be tricky since its callback only receives one previous value. Also, we can peek at the last two values from the callback's last argument, the array being traversed, because that array is immutable (this is functional programming after all).

Fortunately, the programming world is full of magic tricks and secret passages. Among other possibilities, one trick where we can keep using reduce is to use an (empty) array as the initial value. In fact, this array will contain the final Fibonacci series. Since we continue to stash more numbers in that array, looking at the two previous numbers becomes very easy. In fact, the full code for that is not long-winded at all.

function fibo(n) {
  return Array.apply(0, Array(n)).
    reduce(function(x, y, z){ return x.concat((z < 2) ? z : x[z-1] + x[z-2]); }, []);
}

Update: The original version contains map but Jed Schmidt (@jedschmidt) kindly pointed out that it is not necessary because we just want to use the element index and we do not care about the element value itself.

Rewriting the above function to use ECMAScript 6's array comprehension and arrow function is left as an exercise for the reader.

Finally, if you still cast doubt on the power of JavaScript Array object, think about it again. Among mortals second thoughts are the wisest.

  • knappnytt

    I find this very cool, but what I dislike about this is that
    Array.apply(0, Array(n))
    is _completely_ incomprehensible unless you’ve read this article.

    • Seoh Cha

      fyi, http://www.2ality.com/2013/07/array-iteration-holes.html

      if i understand what you are saying, this article may imply between
      Array(10).map(function(e,i,arr){console.log(i);});
      and
      Array.apply(null, Array(10)).map(function(e,i,arr){console.log(i);});

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

        I already explained the story on Array.apply(0, Array(n)) in depth, see the previous blog post (also linked in this current article): “Sequences using JavaScript Array” at http://ariya.ofilabs.com/2013/07/sequences-using-javascript-array.html.

      • http://ecmazing.com/ Šime Vidas

        In a nutshell, Array(10) initializes an array, sets its length to 10, but doesn’t add any elements to the array. So, the array has *no elements* (@ariya:disqus wink-wink :P). Hence, the map method won’t execute the callback, since there are no elements to iterate over.

        That Array.apply pattern makes sure that the elements are added to the array. The values of those elements will be undefined, but that doesn’t matter, since we only need the presence of those elements. Since the array now has 10 elements, the map method will execute the callback 10 times.

  • colin

    Nice
    What exactly does the “~~” trick do and where can I find more information on it?

  • Steven Black

    “Every JavaScript programmer worth her salt”

    I hate to a troll, but I thought we were supposed to use “s/he” or “his or her” from now on to be more inclusive. I do a lot of writing for my company, so could someone clue me in on what is the best way to go in a situation like this one?? I know the last couple times I used “his” by itself I got ripped for it! thanks!

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

      There’s a discussion about this in the past, but I can’t recall the link again.

      In general, I often choose to follow Ben Horowitz’s style, see http://bhorowitz.com/2013/03/04/staying-great/ or his previous blog posts.

  • Saebekassebil

    I think writing a range(n) method at the beginning of this article would help its readability a lot – But nevertheless a great way of showing the process of converting loops to array iterations using functions.

  • lynxluna

    I’ve been working with functional programming with scala for a few weeks for server side logic. And recently doing some Web stuff using Javascript (err.. actually it’s Coffeescript).

    I wonder how to do FP with JS, this example provide a clear usage of FP in Array object. Your other references on creating sequences is very helpful too.

    Maybe a little out of topic, but one question,
    I’m not familiar now on how JS manage their objects, but if I strive using immutable objects, how do JS manage my ‘old object’?

  • Dima Vidmich

    fyi Array.apply(0, Array(N)) is exactly the same as Array(N)

    • Dima Vidmich

      damn, I’m wrong. map on just Array(N) will not call function at all cause all indexes are unused.

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

        Just read my previous blog post (already linked above): Sequences using JavaScript Array. It’s already explained there.