How to implement a generator function in JS (iteration protocols)
Tags: tutorial, javascript, webdev
Published: 2021-01-08 16:21:20

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:

{% youtube akKQpl2uCIg %}

## 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: <br>`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](https://dev-to-uploads.s3.amazonaws.com/i/oinbzfzapkpxn7vc6gko.png)
 

## 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](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols#the_iterator_protocol) is defined)

```js
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
```

## `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](https://dev.to/crayoncode/how-to-implement-the-iterator-and-iterable-protocols-and-make-your-own-objects-work-with-for-of-355n):

{% youtube gjMD4SsGD9w %}

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:

```js
const iterator = someIterable[Symbol.iterator]();
```

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.

```js
for (const value of someIterable) {
    console.log(value);
}
```

## A generator function for a custom doubly linked list

> See the full code at <br> https://github.com/crayon-code/js-doublylinkedlist-generator
> The code given here is based on the previous episode mentioned in [The previous episode](https://dev.to/crayoncode/how-to-implement-the-iterator-and-iterable-protocols-and-make-your-own-objects-work-with-for-of-355n)

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:

```js
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
    }
  }
}
```

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

```js
const dll = new DoublyLinkedList();
...

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

}
```

## Iterating in reverse direction

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

```js
class DoublyLinkedList {
  ...
  
  *reverse() {
    let current = this.tail;
    while (current) {
      const { value, prev } = current;
      current = prev;
      yield value;
    }
  }
}
```
... which is also used quite easily:

```js
const dll = new DoublyLinkedList();
...

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

}
```