DEV Community

Cover image for How to implement a generator function in JS (iteration protocols)
crayoncode
crayoncode

Posted on • Updated on

How to implement a generator function in JS (iteration protocols)

Quickly get a grasp on how to build a generator function in JS and how to use the yield keyword.

Read the full article or watch me code this on Youtube:

In a Nutshell

  • A generator function allows us to write leaner implementations of the iterable and iterator protocols compared to implementing them "by hand".
  • A generator function is defined by putting an asterisk right after the function keyword: function* myGenerator() { ... }
  • Everytime a generator function is called, it returns a Generator object - which is in turn an instance of the called generator function. So the code of a generator function actually defines how that Generator object works.
  • The Generator object implements both iterable and iterator protocols and can therefore be used in conjunction with for ... of ... loops. This is a (but not the only) major use case of Generator objects.
  • The mechanics behind generator function/object can be seen as some sort of stateful function. It memorizes where code execution was interrupted and continues from there on upon the subsequent call.
  • The yield keyword is what makes this possible. Use it instead of and like the return keyword. It returns the given value to the caller, interrupts execution of the generator function and memorizes where it needs to continue.

Generator functions in a nutshell

Basics

A generator function can be seen as an alternative to create an iterator object and as some sort of stateful function.

Whenever you call a function it runs from start to end and if during execution a return statement is encountered, the given value is returned to the caller. If you call that same function again, it also again runs from start to end.

With generator functions it's slightly different. It can be interrupted and continued upon subsequent calls. The keyword that enables us to do so, is the so called yield statement. It works just like a return statement, so the value given to it, is returned to the caller. But, it also memorizes the state of the function and the position of code execution. This means that if the generator function is called again, it continues execution just after the yield statement which has been executed last.

So for the following generator function to be fully executed from start to end, four calls are necessary. The first three calls are there to retrieve the three given values and fourth call is there to terminate the iterator (see how the next() function is defined)

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

let generator = myGenerator();
console.log(generator.next().value); // 1
console.log(generator.next().value); // 2
console.log(generator.next().value); // 3
console.log(generator.next().value); // undefined
Enter fullscreen mode Exit fullscreen mode

iterable/iterator Protocols and for ... of ...

Heads up: If you're not familiar with iterators and/or the iterable/iterable protocols, it may be helpful watching the previous episode:

JS offers two protocols called iterable and iterator. Any object that implements the iterable protocol (such as arrays), can for instance be used in a for ... of ... loop to iterate over the content of that given object. The iterable and iterator protocols are tightly connected, as an iterable object is required to provide an iterator by exposing a zero-argument function in terms of a property accessible through Symbol.iterator. As complicated as this sounds, it's simply put into a single line of code:

const iterator = someIterable[Symbol.iterator]();
Enter fullscreen mode Exit fullscreen mode

But not always you would want to work with the iterator directly, as e.g. the for ... of ... loop implicitly deals with iterables. In the following example someIterable[Symbol.iterator]() is called by the runtime and the resulting iterator is used to run the for ... of ... loop.

for (const value of someIterable) {
    console.log(value);
}
Enter fullscreen mode Exit fullscreen mode

A generator function for a custom doubly linked list

See the full code at
https://github.com/crayon-code/js-doublylinkedlist-generator
The code given here is based on the previous episode mentioned in The previous episode

A doubly linked list is a sequence of nodes, in which each node knows its predecessor and successor. So internally each node has a property for the actual value (called value) and a property for each the predecessor (called previous) and the successor (called next).

The first node of a doubly linked list is called head and the last one tail.

So to write a generator function that enables us to iterate from start to end of the doubly linked list, only a few lines of code are required:

class DoublyLinkedList {
  ...

  // function definitions in a class
  // do not require the function
  // keyword, so only the asterisk
  // is written in front of the 
  // function identifier
  *[Symbol.iterator]() {

    // start iterating at the head
    let current = this.head;

    // current is falsy as soon as 
    // the last item was passed 
    // (or the list is empty)
    // so the loop would terminate 
    // (or not even start)
    while (current) {

      // retrieve the reference 
      // to the next item as well as
      // the current value
      const { next, value } = current;

      // advance current to the
      // (potentially) next item
      current = next;

      // and (statefully) return the
      // current value to the caller
      yield value;

      // and right after the yield 
      // statement code execution
      // is continued, so the next
      // thing that happens is the
      // re-evaluation of the
      // loop condition
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

And from there on it's really simply to use:

const dll = new DoublyLinkedList();
...

// Now this implicitly uses
// the generator function behind
// [Symbol.iterator]
for (const item in dll) {

}
Enter fullscreen mode Exit fullscreen mode

Iterating in reverse direction

Additionally it's quite easy to write a generator function that just iterates the list from last to first item...

class DoublyLinkedList {
  ...

  *reverse() {
    let current = this.tail;
    while (current) {
      const { value, prev } = current;
      current = prev;
      yield value;
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

... which is also used quite easily:

const dll = new DoublyLinkedList();
...

// Note the call to reverse()
for (const item in dll.reverse()) {

}
Enter fullscreen mode Exit fullscreen mode

Top comments (1)