JavaScript for impatient programmers (beta)
Please support this book: buy it or donate
(Ad, please don’t block.)

35. Synchronous generators (advanced)



35.1. What are synchronous generators?

Synchronous generators are special versions of function definitions and method definitions that always return synchronous iterables:

// Generator function declaration
function* genFunc1() { /*···*/ }

// Generator function expression
const genFunc2 = function* () { /*···*/ };

// Generator method definition in an object literal
const obj = {
  * generatorMethod() {
    // ···
  }
};

// Generator method definition in a class definition
// (class declaration or class expression)
class MyClass {
  * generatorMethod() {
    // ···
  }
}

Asterisks (*) mark functions and methods as generators:

35.1.1. Generator functions return iterables and fill them via yield

If you call a generator function, it returns an iterable (actually: an iterator that is also iterable). The generator fills that iterable via the yield operator:

function* genFunc1() {
  yield 'a';
  yield 'b';
}

const iterable = genFunc1();
// Convert the iterable to an Array, to check what’s inside:
assert.deepEqual([...iterable], ['a', 'b']);

// You can also use a for-of loop
for (const x of genFunc1()) {
  console.log(x);
}
// Output:
// 'a'
// 'b'

35.1.2. yield pauses a generator function

So far, yield looks like a simple way of adding values to an iterable. However, it does much more than that – it also pauses and exits the generator function:

Let’s examine what that means via the following generator function.

let location = 0;
function* genFunc2() {
  location = 1;
  yield 'a';
  location = 2;
  yield 'b';  
  location = 3;
}

The result of a generator function is called a generator object. It is more than just an iterable, but that is beyond the scope of this book (consult “Exploring ES6” if you are interested in further details).

In order to use genFunc2(), we must first create the generator object genObj. genFunc2() is now paused “before” its body.

const genObj = genFunc2();
// genFunc2() is now paused “before” its body:
assert.equal(location, 0);

genObj implements the iteration protocol. Therefore, we control the execution of genFunc2() via genObj.next(). Calling that method, resumes the paused genFunc2() and executes it until there is a yield. Then execution pauses and .next() returns the operand of the yield:

assert.deepEqual(
  genObj.next(), {value: 'a', done: false});
// genFunc2() is now paused directly after the first `yield`:
assert.equal(location, 1);

Note that the yielded value 'a' is wrapped in an object, which is how iterables always deliver their values.

We call genObj.next() again and execution continues where we previously paused. Once we encounter the second yield, genFunc2() is paused and .next() returns the yielded value 'b'.

assert.deepEqual(
  genObj.next(), {value: 'b', done: false});
// genFunc2() is now paused directly after the second `yield`:
assert.equal(location, 2);

We call genObj.next() one more time and execution continues until it leaves the body of genFunc2():

assert.deepEqual(
  genObj.next(), {value: undefined, done: true});
// We have reached the end of genFunc2():
assert.equal(location, 3);

This time, property .done of the result of .next() is true, which means that the iterable is finished.

35.1.3. Why does yield pause execution?

What are the benefits of yield pausing execution? Why doesn’t it simply work like the Array method .push() and fill the iterable with values – without pausing?

Due to pausing, generators provide many of the features of coroutines (think processes that are multitasked cooperatively). For example, when you ask for the next value of an iterable, that value is computed lazily (on demand). The following two generator functions demonstrate what that means.

/**
 * Returns an iterable over lines
 */
function* genLines() {
  yield 'A line';
  yield 'Another line';
  yield 'Last line';
}

/**
 * Input: iterable over lines
 * Output: iterable over numbered lines
 */
function* numberLines(lineIterable) {
  let lineNumber = 1;
  for (const line of lineIterable) { // input
    yield lineNumber + ': ' + line; // output
    lineNumber++;
  }
}

Note that the yield inside numberLines() appears inside a for-of loop. yield can be used inside loops, but not inside callbacks (more on that later).

Let’s combine both generators to produce the iterable numberedLines:

const numberedLines = numberLines(genLines());
assert.deepEqual(
  numberedLines.next(), {value: '1: A line', done: false});
assert.deepEqual(
  numberedLines.next(), {value: '2: Another line', done: false});

Every time we ask numberedLines for another value via .next(), numberLines() only asks genLines() for a single line and numbers it. If genLines() were to synchronously read its lines from a large file, we would be able to retrieve the first numbered line as soon as it is read from the file. If yield didn’t pause, we’d have to wait until genLines() is completely finished with reading.

  Exercise: Turning a normal function into a generator

exercises/generators/fib_seq_test.js

35.1.4. Example: Mapping over iterables

The following function mapIter() is similar to Array.from(), but it returns an iterable, not an Array and produces its results on demand.

function* mapIter(iterable, func) {
  let index = 0;
  for (const x of iterable) {
    yield func(x, index);
    index++;
  }
}

const iterable = mapIter(['a', 'b'], x => x + x);
assert.deepEqual([...iterable], ['aa', 'bb']);

  Exercise: Filtering iterables

exercises/generators/filter_iter_gen_test.js

35.2. Calling generators from generators (advanced)

35.2.1. Calling generators via yield*

yield only works directly inside generators – so far we haven’t seen a way of delegating yielding to another function or method.

Let’s first examine what does not work: In the following example, we’d like foo() to call bar(), so that the latter yields two values for the former. Alas, a naive approach fails:

function* foo() {
  // Nothing happens if we call `bar()`:
  bar();
}
function* bar() {
  yield 'a';
  yield 'b';
}
assert.deepEqual(
  [...foo()], []);

Why doesn’t this work? The function call bar() returns an iterable, which we ignore.

What we want is for foo() to yield everything that is yielded by bar(). That’s what the yield* operator does:

function* foo() {
  yield* bar();
}
function* bar() {
  yield 'a';
  yield 'b';
}
assert.deepEqual(
  [...foo()], ['a', 'b']);

In other words, the previous foo() is roughly equivalent to:

function* foo() {
  for (const x of bar()) {
    yield x;
  }
}

Note that yield* works with any iterable:

function* gen() {
  yield* [1, 2];
}
assert.deepEqual(
  [...gen()], [1, 2]);

35.2.2. Example: Iterating over a tree

yield* lets us make recursive calls in generators, which is useful when iterating over recursive data structures such as trees. Take, for example, the following data structure for binary trees.

class BinaryTree {
  constructor(value, left=null, right=null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }

  /** Prefix iteration: parent before children */
  * [Symbol.iterator]() {
    yield this.value;
    if (this.left) {
      // Same as yield* this.left[Symbol.iterator]()
      yield* this.left;
    }
    if (this.right) {
      yield* this.right;
    }
  }
}

Method [Symbol.iterator]() adds support for the iteration protocol, which means that we can use a for-of loop to iterate over an instance of BinaryTree:

const tree = new BinaryTree('a',
  new BinaryTree('b',
    new BinaryTree('c'),
    new BinaryTree('d')),
  new BinaryTree('e'));

for (const x of tree) {
  console.log(x);
}
// Output:
// 'a'
// 'b'
// 'c'
// 'd'
// 'e'

  Exercise: Iterating over a nested Array

exercises/generators/iter_nested_arrays_test.js

35.3. Example: Reusing loops

One important use case for generators is extracting and reusing loop functionality.

35.3.1. The loop to reuse

As an example, consider the following function that iterates over a tree of files and logs their paths (it uses the Node.js API for doing so):

function logFiles(dir) {
  for (const fileName of fs.readdirSync(dir)) {
    const filePath = path.resolve(dir, fileName);
    console.log(filePath);
    const stats = fs.statSync(filePath);
    if (stats.isDirectory()) {
      logFiles(filePath); // recursive call
    }
  }
}
const rootDir = process.argv[2];
logFiles(rootDir);

How can we reuse this loop, to do something other than logging paths?

35.3.2. Internal iteration (push)

One way of reusing iteration code is via internal iteration: Each iterated value is passsed to a callback (line A).

function iterFiles(dir, callback) {
  for (const fileName of fs.readdirSync(dir)) {
    const filePath = path.resolve(dir, fileName);
    callback(filePath); // (A)
    const stats = fs.statSync(filePath);
    if (stats.isDirectory()) {
      iterFiles(filePath, callback);
    }
  }
}
const rootDir = process.argv[2];
const paths = [];
iterFiles(rootDir, p => paths.push(p));

35.3.3. External iteration (pull)

Another way of reusing iteration code is via external iteration: We can write a generator that yields all iterated values.

function* iterFiles(dir) {
  for (const fileName of fs.readdirSync(dir)) {
    const filePath = path.resolve(dir, fileName);
    yield filePath; // (A)
    const stats = fs.statSync(filePath);
    if (stats.isDirectory()) {
      yield* iterFiles(filePath);
    }
  }
}
const rootDir = process.argv[2];
const paths = [...iterFiles(rootDir)];

35.4. Advanced features of generators