Elegant iteration in JavaScript with generators
Tags: datastructures, javascript
Published: 2019-04-09 01:52:35

---
title: Elegant iteration in JavaScript with generators
published: true
description: Use JavaScript generators with data-structures
tags: datastructures, datastructures, javascript
---

In the past, iteration in JavaScript often involved while loops, for-loops, and recursions. Eventually, programmers have devised patterns for the purposes of iterations. One such pattern is the [iterator pattern](https://en.wikipedia.org/wiki/Iterator_pattern).

It is such a powerful yet elegant pattern, that it became a core part of the JavaScript programming language.

In this article, I will go over generators, iterables, and iterators, and how you can apply them in retrieving data from your data structures.

## Generators primer

Generators are a way to *generate* a series of values, or to *run* a series of operations. That series can either eventually stop, or go on forever.

This is how you would write a generator:

```javascript
function * myGenerator() {
  yield 1;
  yield 2;
  yield 3;
}
```

Unlike functions, when you invoke `myGenerator`, you *don't* immediately get `1`, `2`, and `3`. Instead, you get what is called an *iterable* (actually, it's an iterable-iterator. More on that later). Iterables are core to the JavaScript language.

In order to extract those values, you need to *iterate* through the *iterable*. You'd do so via the `for-of` loop.

```javascript
const iterable = myGenerator();

for (const value of iterable) {
  console.log(value);
}

// Should give us:
// 1
// 2
// 3
```

But, if you wanted to turn that iterable into an array, you don't need to use `for-of`; instead, you can just ["spread"](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Spread_syntax) it into an array.

```javascript
const iterable = myGenerator();

const fromIterable = [...iterable];
```

The versatility of iterables in JavaScript is why this pattern makes it so powerful. In fact, so many constructs in JavaScript either accept iterables, or are, themselves, iterables! Arrays, for instance, are defined as iterables.

If you wanted to, you can "spread" the iterable to a list of parameters.

```javascript
someSpreadable(...iterable);
```

Arrays aren't exclusive to function spread operator; *iterables*, in general, can have the spread operator applied.

With generators, not only can you "yield" a single value, but you can also "yield" the *individual* values enclosed in an iterable. And so, you can rewrite the above `myGenerator` function to "yield" the individual `1`, `2`, and `3`, but instead from an array. Just be sure to append a `*` right after the `yield` keyword.

```javascript
function * myGenerator() {
  yield * [1, 2, 3];
}
```

### Infinite series

If you wanted to generate an infinite series, you can create a generator to do so. It will involve while loop, but once done so, you can apply whatever helpers you'd need to extract the necessary values. Let's generate the Fibonacci sequence.

```javascript
function * fibonacci() {
  let previous = 0;
  let i = 1;
  while (true) {
    previous = i + previous;
    yield previous;
  }
}
```

And, to take the first ten elements of the sequence, we can write a generator for that.

```javascript
function * take(iterable, n) {
  let i = 0;
  for (let value of iterable) {
    yield value;
    i++;
    if (i >= n) { break; }
  }
}
```

Afterwards, we can get the first ten values of the fibonacci sequence.

```javascript
const iterator = take(fibonacci(), 10);
console.log([...iterator]);
// -> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
```

Generally, you won't re-invent the wheel. The above `take` implementation already exists within the [IxJS library](https://github.com/ReactiveX/IxJS). Perhaps, in the future, there may even be helper functions [built right into JavaScript](https://github.com/tc39/proposal-iterator-helpers/issues/8).

## Iterables and iterators

In the previous section, generators were discussed. Generators are functions that return iterables. Iterables are objects that have a method that is keyed by `Symbol.iterator`. The existence of that method signals to various JavaScript constructs that an object is an iterable. The `Symbol.iterator` method is what returns an *iterator*. The iterator object implements a `next` method, which itself returns an object that has the properties `value` and `done`.

The property `value` represents the value in the current iteration; `done` is a boolean value to indicate if the iterations is complete.

The following is an example implementation of an object that is iterable, and that returns a series of number `1`, forever.

```javascript
const someIterable = {
  [Symbol.iterator]() {
    return {
      next() {
        return { value: 1, done: false }
      }
    }
  }
}
```

In the previous section on generators, it was mentioned that generators return an iterable. That is, however, not entirely true. They actually return an "iterable-iterator". That is, they are both an iterable, and an iterator. And so, we can use a generator to define the above `Symbol.iterator` method.

Here's the implementation using generators.

```javascript
const someIterable = {
  *[Symbol.iterator]() {
    while (true) {
      yield 1;
    }
  }
}
```

Both implementations are almost identical.

## Data structures

If you needed to store and retrieve data efficiently, you can use a tree-like structure. However, if you needed to iterate through the values, you'd need to traverse the tree.

Generators can facilitate this. We'll use a [binary search tree](https://en.wikipedia.org/wiki/Binary_search_tree) to demonstrate this (here's an animation for this https://youtu.be/qHCELlYY08w?t=22).

Tree data structures have nodes. It's through nodes that we traverse the entire tree. Generators can facilitate recursive descent, and so, we can have the node itself be an iterable! Both the left and right nodes are thus iterables (since they represent left and right subtrees, respectively); we can "yield" their values.

```javascript
class Node {
  // ... let's ignore the implementation of `Node`

  *[Symbol.iterator]() {
    if (this.left !== null) { yield * this.left; }
    yield this.value;
    if (this.right !== null) { yield * this.right; }
  }
}
```

Likewise, binary search tree itself can "yield" the root node.

```javascript
class BinarySearchTree {
  // ... let's ignore the implementation of the tree

  *[Symbol.iterator]() {
    if (this.root !== null) { yield * this.root; }
  }
}
```

We can, therefore, use the binary search tree like so:

```javascript
const tree = new BinarySearchTree();

tree.insert(10, 'bar');
tree.insert(3, 'foo');
tree.insert(11, 'baz');

console.log([...tree]);
// -> [ 'foo', 'bar', 'baz' ]
```

## Other examples of iterables

As far as iterables are concerned, it's already been mentioned that generators return iterables, that arrays are iterables, and that the above binary search tree is an example of a custom iterable. JavaScript has two other defined constructs that are iterables, which are [`Map`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map), and [`Set`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set)

We can take Map or Set, and interact with them the same way we would with other iterables.

## Conclusion

Iterables are a core feature in JavaScript. They are a way to generate values, which you can iterate through individually. They are an expressive way to expose an object's underlying set of values. Because they are a core to JavaScript, they are used heavily by many of the language's constructs, and future JavaScript revisions will continue to use iterables, in potentially new syntaxes.

So instead of relying on arrays to represent collections, consider defining an object that doubles as an iterable. This way, not only do you grant more power to the user of your code, but you'd likely save on computation by only giving what the user code asked, and *only* when asked.