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 === ) 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(undefined, Array(1 + ~~Math.sqrt(i))).
every(function (x, y) { return (y < 2) || (i % y !== ) });
}
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(undefined, Array(N)).map(function (x, y) { return y }).
filter(function (i) {
return (i > 1) && Array.apply(undefined, Array(1 + ~~Math.sqrt(i))).
every(function (x, y) { return (y < 2) || (i % y !== ) });
});
}
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(undefined, Array(N)).map((x, y) => y))
if ((i > 1) && Array.apply(undefined, Array(1 + ~~Math.sqrt(i))).
every((x, y) => (y < 2) || (i % y !== ) ))
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*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(undefined, 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(undefined, 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 = ; 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(undefined, 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.