Generators in JavaScript

Jul 10, 2019

Let’s write a function that let’s us take an n-sized subset of some iterator.

1
function* take(n, iter) {
2
  let index = 0;
3

4
  for (const x of iter) {
5
    if (index >= n) return;
6

7
    index++;
8
    yield x;
9
  }
10
}
11

12
const it = take(3, ["foo", "baz", "bar", "doe", "ray", "me"]);
13
printIterations(it); // foo, baz, bar

Cycling

Imagine you have an array, and you want to cycle through all the values, ad infinitum.

1
function* cycle(array) {
2
  let index = 0;
3

4
  while (true) {
5
    yield array[index];
6
    index = (index + 1) % array.length;
7
  }
8
}
9

10
const it = take(5, cycle([1, 2, 3]));
11
printIterations(it); // 1, 2, 3, 1, 2

Skipping

Now imagine you’re a teacher, and you are going to select a student for a task. However, each time you count, you skip a student.

1
// To skip 1 student means to add 2 with each iteration
2
// To skip n students means to add n+1 with each iteration
3
function* skip(n, array) {
4
  /*
5
   * A teacher would count the first student in the line as "1",
6
   * and arrays are 0 indexed, so starting at -1 correct for that
7
   *
8
   * Notice that if you skip 0 students, you start at the beginning
9
   * of the line, and count normally
10
   */
11
  let index = -1;
12

13
  while (true) {
14
    index = (index + (n + 1)) % array.length;
15
    yield array[index];
16
  }
17
}
18

19
const it = take(
20
  5,
21
  skip(1, [
22
    "Captain America",
23
    "Black Widow",
24
    "Hulk",
25
    "Iron Man",
26
    "Black Panther",
27
  ])
28
);
29
printIterations(it);

// yes, your students are the Avengers. Black Widow
Iron Man Captain America Hulk Black Panther ```

How many times did we have to count until we got back to the start of the array?

```javascript
function* skipUntilMatch(n, array, toFind) {
  let index = -1;
  let count = 1;

  while (true) {
    index = (index + (n + 1)) % array.length;

    if (array[index] === toFind) return count;

    yield;
    count++;
  }
}

const arr = [
  "Captain America",
  "Black Widow",
  "Hulk",
  "Iron Man",
  "Black Panther",
];
const it = skipUntilMatch(1, arr, arr[0]);
exhaustAndGrabLast(it); // 3, i.e. "miney"

Generators

The functions were using above are called generators. They’re special functions that pause execution and yield a value. When they are executed the next() time, execution is resumed, as opposed to done over again, like a normal function. They are done when they finally return.

**Generators** are functions with the ability to pause and resume execution. A generator looks like a function but behaves like an iterator.

This gives us another way to iterate. One of the key functionalities provided is the ability to work with infinite series. When you iterate using a collection, all the values are sitting in memory, so you don’t have that ability.

1
function* naturalNumbers() {
2
  let num = 1;
3

4
  while (true) {
5
    yield num;
6
    num++;
7
  }
8
}
9

10
const it = take(7, naturalNumbers());
11
printIterations(it); // 1, 2, 3, 4, 5, 6, 7
12

13
/* or, if you don't want it to terminate */
14
printIterations(naturalNumbers()); // 1, 2, 3, 4, ...

Halving

Achilles is running a race. Each step is half the length of his previous step. How many steps until he’s not moving at all?

Theoretically, half of any number, ad infinitum, will never reach 0. Only it’s limit does.

However, in a programming language like JS, we’re dealing with finite resources, and that number will at some point reach 0. Let’s find out when.

1
function* halfUntilZero() {
2
  let remaining = 1;
3
  let count = 0;
4

5
  while (true) {
6
    if (remaining == 0) return count;
7

8
    yield;
9
    remaining = remaining / 2;
10
    count++;
11
  }
12
}
13

14
exhaustAndGrabLast(halfUntilZero()); // 1075

Finally, let’s take a look at some of the helper functions we’ve been using. It might be useful to reflect on JavaScript’s iterator protocol.

1
function printIterations(it) {
2
  let i = it.next();
3

4
  while (!i.done) {
5
    console.log(i.value);
6
    i = it.next();
7
  }
8
}
9

10
function exhaustAndGrabLast(it) {
11
  let current = it.next();
12
  let value = current.value;
13

14
  while (!current.done) {
15
    current = it.next();
16
    value = current.value || value;
17
  }
18

19
  return value;
20
}

Sources

Understanding JavaScript Generators, inspired take and naturalNumbers
MDN

Wow! You read the whole thing. People who make it this far sometimes want to receive emails when I post something new.

I also have an RSS feed.