.

Tags:

numbers

Generating a sequence is a common programming task. This is rather easy to achieve using a straightforward loop. With JavaScript however, there exists a more functional variant using the powerful Array object. This permits the generation of all kind of sequences, from A..Z to a list of prime numbers, without any loops at all.

Supposed you are about to create a list of numbers 1, 2, 3 and place it in an array, one possible loop-based implementation is:

var result = [];
for (var i = 1; i != 4; ++i) result.push(i)
console.log(result);  // [1, 2, 3]

Obviously, tweaking the code can yield a different kind of sequence. For example, a sequence of Latin alphabets is a matter of converting each number into the right letter:

var list = '';
for (var i = 0; i != 26; ++i) list += String.fromCharCode(i + 65);
console.log(list);   // 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

Using loops is nice, but can we get the same result sans loops? Fortunately, JavaScript is quite capable of doing it. We just need to rely on its built-in object Array. In the following explanation, all the sections mentioned refer to the Standard ECMA-262, the official ECMAScript Language Specification edition 5.1.

Earth

First of all, we need to create an array which has the specified amount of elements. For that 1,2,3 example, we need a 3-element array. Fortunately, this is trivial:

Array(3);

Note that there is no need to use new for object construction, this is explained in Section 15.4.1:

When Array is called as a function rather than as a constructor, it creates and initialises a new Array object.

Array(3) creates an array with the length of 3, it is the same as [,,,]. The resulting array however has holes in it. In fact, although it has 3 elements, those elements do not exist. Holes like this are not so obvious if you try to peek at the array contents. Compare the two lines:

Array(3).join('-');                // "--"
[null,undefined,null].join('-');   // "--"

We can verify the existence of an array element just like checking for a property in a generic JavaScript object, using the in operator (Section 11.8.7):

0 in Array(3);   // false
1 in Array(3);   // false
2 in Array(3);   // false
2 in [,,9];      // true

As pointed by Axel Rauschmayer, holes inside an array are also detected with forEach.

Water

How to fill those holes? A trick discovered by many seasoned JavaScript developers (see e.g. Brandon Benvie’s post on es-discuss) is to use Array.apply. Instead of some empty elements, now we have undefined to replace them:

Array(3);                  // [,,,]
Array.apply(0, Array(3));  // [undefined, undefined, undefined]

To really understand this trick, recall how Function.prototype.apply works (Section 15.3.4.3), particularly in the Step 8, transforming an array into an argument list for the function, called spreading. No wonder this approach is quite often used to find the minimum or maximum value in an array. In the following fragment, the two lines are identical:

Math.max(14, 3, 77);                 // 77
Math.max.apply(Math, [14, 3, 77]);   // 77

When apply receives an array with an empty element, it gets converted into undefined and thereby eliminates any holes in the array. If we combined it with Array construction, the end effect is constructing a new array with the spread.

Array.apply(0, [1,,3]);  // is the same as
Array(1, undefined, 3);

Air

Now that we have an array with the right number of elements, how do fill it with the right sequence? Array.prototype.map to the rescue! Section 15.4.4.19 shows that:

map calls callbackfn once for each element in the array, in ascending order, and constructs a new Array from the results.

Further down, we also observe that:

callbackfn should be a function that accepts three arguments. callbackfn is called with three arguments: the value of the element, the index of the element, and the object being traversed.

The second argument, the index of the element, is the key to our solution:

Array.apply(0, Array(3)).map(function (x, y) { return y + 1; });  // [1, 2, 3]

And if the sequence is about the squares of the first few integers:

Array.apply(0, Array(3)).map(function (x, y) { return (y + 1) * (y + 1); });

Finally, for the English alphabets ‘ABCDEFGHIJKLMNOPQRSTUVWXYZ’:

Array.apply(0, Array(26)).map(function(x,y) {
  return String.fromCharCode(y + 65);
}).join('');

For alternatives to using map, see also Brandon Benvie’s usage of Function.call with Number or Ben Alman’s solution with Object.keys.

Fire

With the new array comprehension feature of the forthcoming ECMASCript 6, the above one-liners can be slightly tweaked. For example, the alphabets sequence might be written as (note the use of arrow function):

[for (i of Array.apply(0, Array(26)).map((x, y) => y))
String.fromCharCode(65 + i)].join('');

Here the conversion from each number to the corresponding letter is carried out outside the map callback. This makes the code easier to digest, it resembles a proper composition: generate the sequence first and do another step to transform the sequence. For details, check out my previous blog post (with tons of examples) on ECMAScript 6 and Array Comprehension.

Loops are overrated, aren’t they?

Addendum: As a follow-up, see also how you can use the same approach to generate a list of prime numbers, compute the factorial, and produce the Fibonacci series in the new blog post: Prime Numbers, Factorial, and Fibonacci Series with JavaScript Array.

  • Bill

    Now I wonder if one couldn’t create lazy sequences using this trick and generators… interesting.

  • ricardobeat

    A little trick to generate sequences cleanly, without ‘leaking’ an index variable: for(var a=[]; a.length < 10; a.push(a.length)); a

    There is a nice article on other array tricks here, you can do some pretty cool stuff using Function::call/apply and array methods: http://net.tutsplus.com/tutorials/javascript-ajax/what-they-didnt-tell-you-about-es5s-array-extras/

    • andre

      the problem is that it checks twice the array’s length..

      • ricardobeat

        array.length is used as the counter in this case. The performance hit is negligible for reasonably sized arrays. It’s just a neat trick in any case, I haven’t actually used that in an application :)

    • Ray Bellis

      I created this recursive sequence generator last year that I was quite proud of:


      Array.range = function f(m, n, z) {
      return m <=-- n ? (z = f(m, n), z.push(n), z) : []
      };

      particularly for managing to include the “firework operator” :)

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

    “In fact, although it has 3 elements, those elements do not exist.”
    This should be rewritten I think :) The spec doesn’t define non-existent elements.

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

      Care to elaborate?

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

        An array either has elements or it doesn’t have elements. In the case of Array(3), the resulting array will have no elements. You’re saying that the array will have 3 non-existent elements. This doesn’t make sense I think. I’m not sure what you mean by “non-existent elements”. If the elements don’t exist, then there are no elements in the first place, i.e. the array has no elements.

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

          Ah, semantics issue. I can’t find the best, non-ambiguous way to explain this, in particular because there’s not enough expression (at least in English) to portray the situation. Hence, I picked the less confusing one.

          If I say “Array(3) has no elements”, that contradicts immediately with the fact that its ‘length’ is 3 and when you dump the value it says ‘[,,]‘.

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

            This is a case where the “length” property *doesn’t* reflect the number of array elements. The spec is clear about this (15.4.2.2). Array(3) will initialize a new array, set its “length” to 3 but won’t create any elements on the array. So, it creates an array that has no elements and at the same time has a non-zero “length” value. I think that, when explicitly stated, this is not confusing.

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

            As I said, we can argue till tomorrow morning about semantics. At the end of the day, this is a blog post and not a normative text on the specification. I need to strike a balance between being technically faithful and being attractive enough to the laymen. It’s my preference not to venture in a certain path, and thus the use of “non-existing”, “holes”, and “existence”.

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

            This is not about semantics. Your article contains an incorrect statement. (This: “…although it has 3 elements…”.)

            In the future, it would be nice if I could point out incorrect statements in your article without having to argue about the meaning of the word “has” and whatnot. Thank you.

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

            I appreciate your mastery of the specification and your feedback to the matter.

            I never want to argue about this. I simply pointed out that a writer has a little bit of freedom to wander outside the realm of technical correctness, in particular if one wants to relate to colloquial expression of the language.

  • Johan Thelin

    Are there any performance gains or penalties for not using the head on for loop based approach? It looks to me as if you loop multiple times using this method, albeit indirectly.

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

      Using the head?

      • Johan Thelin

        Autocorrect. Sorry about that. So, what is the performance compared to classic loops?

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

          I never measured it. However, for a very small example like this, a straight and simple loop will be always faster.
          Fortunately, people use functional style programming not because of the speed :)

  • Michael Ficarra

    Two nits:

    * [,,] is not Array(3), but Array(2). It’s mentioned a couple times. You have to watch out for those insignificant trailing commas.

    * Math.max(14, 3, 77); is not equivalent to Math.max.apply(this, [14, 3, 77]); , but instead Math.max.apply(Math, [14, 3, 77]);

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

      Corrected. Thanks for the notice!

  • NULL

    You could simplify your english alphabet to:

    String.fromCharCode.apply(String, Array.apply(null, Array(26)).map(function(v,k) {return k+65;}));

    Using the same approach i would say.

  • Ti nk

    Have to say I agree with Šime on this one, but whatever, if you don’t want to change it, Šimes’ comment at least describes the correct implementation.

    You didn’t reply to Johan’s comment on performance. I’m interested in why you would take this approach, are there performance gains?

  • Ivan Jouikov

    So calling a function 26 times to build alphabet is better than doing it in a loop why? These are interesting insights into some clever JS manipulations, but I’m guessing this will not make it into “JavaScript: The Good Parts”? :)

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

      It’s a different style, this is about functional programming.

  • scusyxx

    Great post but I think I am confused about the following lines. Can you please clarify?

    [,,,].length // 3 WHY? there are 4 elements right?

    [,,,].join (“-“) // “–” ???? WHY NOT “—“?
    [1,2,3,4].join (“-“) // 1-2-3-4

  • Ryan Seddon

    You could also simplify some of your examples and utilise ES6 spreads e.g

    [...Array(3)].map(function (x, y) { return (y + 1) * (y + 1); });

    [...Array(26)].map(function(x,y) {
    return String.fromCharCode(y + 65);
    }).join('');

  • esimov

    Another way using Array.prototype.map

    Array.prototype.map.call(Array.apply(0, Array(26)), function(v,x) {return String.fromCharCode(x+65);}).join('');

  • Eli

    I don’t understand why no one made a comment on Array.apply. I didn’t know that Array has apply method.

  • Guest

    Array(10).map(new Function) :F

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

      How is it different than just Array(10)?

  • Mike

    This post was very helpful as I make the transition to writing things in a more functional way. Your description holes and the necessity of array.apply() was a huge help to me as I kept trying to do array(3).map() and I couldn’t understand why an empty array had NO INDEXES as well as no values!

  • Bob Myers

    An alternative is `Array(26).fill()`, which is a bit shorter and perhaps more readable.

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

      For ES6 environment, sure.