308H.10 - Iterators and Generators


Learning Objectives

By the end of this lesson, learners will be able to:

  • Define iterators, iterables, and generators.
  • Construct custom iterators.
  • Use generator functions to construct iterable iterators.
  • Construct custom iterables by implementing the [Symbol.iterator]() method.
  • Use next() and for...of to iterate through iterables.
  • Create async iterables.

 CodeSandbox

This lesson uses CodeSandbox as one of its tools.

If you are unfamiliar with CodeSandbox, or need a refresher, please visit our reference page on CodeSandbox for instructions on:

  • Creating an Account
  • Making a Sandbox
  • Navigating your Sandbox
  • Submitting a link to your Sandbox to Canvas

Iterators

We've already covered the topic of iteration, but it likely won't surprise you to hear that there is always more to know.

Iterators allow us to create objects that can define sequences of information in a controllable way, allowing us to customize the behavior of loops that use them. Here's a rough anology to help you understand the purpose of iterators: functions are used to organize and reuse actions, classes are used to organize and reuse objects, and iterators are used to organize and reuse loops (and loop-like behavior).

Iterators by definition are any object that implements the iterator protocol by including a next() method.

The next() method accepts either zero or one argument, and returns an object conforming to the IteratorResult interface, which has the following properties:

  • done (optional) - A boolean that's false if the iterator was able to produce the next value in the sequence. (This is equivalent to not specifying the done property altogether.) Has the value true if the iterator has completed its sequence. In this case, value optionally specifies the return value of the iterator.
  • value (optional) - Any JavaScript value returned by the iterator. Can be omitted when done is true.

If an object without either result is returned, it is functionally equivalent to { done: false, value: undefined }.

The argument of next() can be a value which will be made available to the method body, as is standard.

Iterators can also implement the return(value) optional method, which is a function that accepts zero or one argument and returns an object conforming to the IteratorResult interface, typically with value equal to the value passed in and done equal to true. Calling this method tells the iterator that the caller does not intend to make any more next() calls and can perform any cleanup actions.

As another optional method, they can implement throw(exception), which is also a function that accepts zero or one argument and returns an object conforming to the IteratorResult interface, typically with done equal to true. Calling this method tells the iterator that the caller detects an error condition, and exception is typically an Error instance.

Once created, iterators can be iterated by explicitly calling the next() method. Iterating over an iterator is said to "consume" the iterator, because it is generally only possible to do so once. Once { done: true } has been sent, all additional calls to next() should also return { done: true }.

You are already familiar with some iterators, the most common of which being the Array iterator, which returns each value in the associated array in sequence.

For example, this code...

const arr = [1, 2, 3, 4, 5];

for (const a of arr) {
    console.log(a);
}

...is functionally equivalent to this:

const arr = [1, 2, 3, 4, 5];
const arrIter = arr[Symbol.iterator]();

let a = arrIter.next();
while (!a.done) {
    console.log(a.value);
    a = arrIter.next();
}

Feel free to follow along in your own sandbox to experiment with how these results are achieved.

This is a type of abstraction in which the inner workings of for...of are unknown to us, and don't need to be known! Understanding them, however, allows us to achieve higher levels of customization and solve problems we otherwise would struggle with.

In this case, the for...of loop automatically calls the array[Symbol.iterator]() method, which returns a new iterable iterator object that yields the value of each index in the array. Strings, as you may have guessed, also work in this way.

So how do we make an "iterable iterator"?

Let's look at an example from the MDN documentation. Say we have a need for an object that counts from a starting value to an ending value using a specific step size.

function makeRangeIterator(start = 0, end = Infinity, step = 1) {
  let nextIndex = start;
  let iterationCount = 0;

  const rangeIterator = {
    next() {
      let result;
      if (nextIndex < end) {
        result = { value: nextIndex, done: false };
        nextIndex += step;
        iterationCount++;
        return result;
      }
      return { value: iterationCount, done: true };
    },
  };
  return rangeIterator;
}

Here, we've defined default starting and ending values, as well as a default step size. The next() method builds the IteratorResult object and returns it. If, however, we have reached the end value, it returns "done" with a value equal to the number of iterations completed.

This is how we would use this iterator (be careful going to Infinity!):

const it = makeRangeIterator(1, 10, 2);

let result = it.next();
while (!result.done) {
  console.log(result.value); // 1 3 5 7 9
  result = it.next();
}

console.log("Iterated over sequence of size:", result.value); // [5 numbers returned, that took interval in between: 0 to 10]

This example has many flaws, not the smallest of which is that it's not yet iterable!

What do we mean the iterator isn't iterable? Well, how exactly would you go about using this in a for...of loop?

const it = makeRangeIterator(1, 10, 2);

for (const val of it) {
    console.log(val);
}

If we try to execute the code above, we get a TypeError that reads "Invalid attempt to iterate non-iterable instance. In order to be iterable, non-array objects must have a [Symbol.iterator]() method."

We'll talk about how to make a custom iterable to fix this problem shortly, but first let's talk about how generator functions can help simplify the process of making iterators.


Generator Functions

Generator functions allow us to avoid the necessity of carefully maintaining the internal state of an iterator. They do this by allowing us to define an iterative algorithm by writing a single function whose execution is not continuous.

When called, generator functions do not initially execute their code. Instead, they return a special type of iterator, called a Generator. When a value is consumed by calling the generator's next() method, the Generator function executes until it encounters the yield keyword.

The function can be called as many times as desired, and returns a new Generator each time. Each Generator may only be iterated once.

Generators are created using the function keyword with an asterisk appended: function*.

Let's adapt the previous example to illustrate this concept. The behavior of the following code is identical, but the implementation is much cleaner.

function* makeRangeIterator(start = 0, end = Infinity, step = 1) {
  let iterationCount = 0;
  for (let i = start; i < end; i += step) {
    iterationCount++;
    yield i;
  }
  return iterationCount;
}

Now, let's try calling this in the same way we called the previous example:

const it = makeRangeIterator(1, 10, 2);

let result = it.next();
while (!result.done) {
  console.log(result.value); // 1 3 5 7 9
  result = it.next();
}

console.log("Iterated over sequence of size:", result.value); // [5 numbers returned, that took interval in between: 0 to 10]

As expected, this works.

Something else has happened, though! If we replace the while loop structure with our previous for...of loop:

for (const val of it) {
    console.log(val);
}

This also works! Generator functions return an iterable iterator!

However! It is very important to highlight a point made earlier: each Generator may only be iterated once.

If we put a second for...of loop beneath our first, what happens?


Custom Iterables

There are a couple of ways to create custom iterable objects, one of which circumvents the "single use" problem.

We could just make an iterator also iterable by implementing the [Symbol.iterator] method and returning this, since it already has next(). Let's look at the original rangeIterator to see how this would be accomplished:

function makeRangeIterator(start = 0, end = Infinity, step = 1) {
  let nextIndex = start;
  let iterationCount = 0;

  const rangeIterator = {
    next() {
      let result;
      if (nextIndex < end) {
        result = { value: nextIndex, done: false };
        nextIndex += step;
        iterationCount++;
        return result;
      }
      return { value: iterationCount, done: true };
    },
    [Symbol.iterator]() {
        return this;
    },
  };

  return rangeIterator;
}

This is, however, taking a few steps backwards in order to take one step forward, and it doesn't even solve the issue of single consumption.

Instead, what if we used a generator to create a new iterable each time we called it?

function makeRangeIterator(start = 0, end = Infinity, step = 1) {
  const rangeIterator = {
    *[Symbol.iterator]() {
      let iterationCount = 0;
      for (let i = start; i < end; i += step) {
        iterationCount++;
        yield i;
      }
      return iterationCount;
    }
  };

  return rangeIterator;
}

Test this by creating multiple for...of loops:

const it = makeRangeIterator(1, 10, 2);

for (const val of it) {
  console.log(val);
}

for (const val of it) {
  console.log(val);
}

It works!

We can also create iterable classes in this way, which allows us to make use of all of the useful properties of classes. For example, here's the same functionality implemented with a class-based approach:

class RangeIterator {
  #start;
  #end;
  #step;

  constructor(start = 0, end = Infinity, step = 1) {
    this.#start = start;
    this.#end = end;
    this.#step = step;
  }
  *[Symbol.iterator]() {
    let iterationCount = 0;
    for (let i = this.#start; i < this.#end; i += this.#step) {
      iterationCount++;
      yield i;
    }
    return iterationCount;
  }
}

const it = new RangeIterator(1, 10, 2);

How would we implement this range iterator in a practical way, though? It is unlikely that we'll need a large number of RangeIterator objects. Say we wanted to be able to iterate conveniently over a custom range rather frequently.

Instead of this:

function iterateOverRange(start, end, step, cb) {
    for (let i = start; i <= end; i += step) {
        cb(i);
    }
}

iterateOverRange(5, 10, 2, (result) =>  {
    console.log(`Value = ${result}`);
});

We could do something like this:

function* range(start, end, step) {
    for (let i = start; i <= end; i += step) {
      yield i;
    }
}

for (const result of range(5, 10, 2)) {
    console.log(`Value = ${result}`);
}

Which approach is "better" depends on your requirements and implementation, but iterables tend to have more obvious behavior at a glance.


Iterables and the Spread Operator

As you are already aware, the spread operator ... can be used with any array. It can also be used with any iterable!

We can spread strings:

const hello = "World";

console.log([...hello]); // ["W", "o", "r", "l", "d"]

We can spread iterable objects of our own creation:

const it = new RangeIterator(1, 10, 2);

console.log([...it]); // (5) [1, 3, 5, 7, 9]
console.log(Math.max(...it)); // 9

This convenient syntax allows iterables to be used in concise and effective ways.


Async Iterators

You can also form asynchronous iterators and iterables! In order to do so, you must implement the [Symbol.asyncIterator] method, and your next(), return() and throw() methods must return a Promise.

In order to process async iterables, JavaScript also provides the for await...of loop:

async function* foo() {
  yield 1;
  yield 2;
}

(async function() {
  for await (const num of foo()) {
    console.log(num);
  }
})();

Practical Examples

One of the most common usages for custom iterables is iteration through custom data structures.

For example, we're all familiar with the call stack and event loop. What if we wanted to create something similar that we could control? Well, the stack is just an ordered list of items, and Arrays are also ordered lists. So, our Stack class might look like this:

class Stack extends Array {
  // suspiciously blank
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);

for (const item of stack) {
  console.log(item); // 1, 2, 3
}

We've given our Stack all of the properties of Array through inheritance, but it iterates from start to finish. This is the opposite of how a stack behaves, since it should return the most recent addition to the stack first. Imagine a stack of cards, where each new item is added to the top and taken from the top. Right now, we're dealing from the bottom of the stack!

In order to fix this, we would need to override the Array class's default [Symbol.iterator]() method, like so:

class Stack extends Array {
  *[Symbol.iterator]() {
    for (let i = this.length - 1; i >= 0; i--) {
      yield this[i];
    }
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);

for (const item of stack) {
  console.log(item); // 3, 2, 1
}

Now, our stack iterates as desired.

If we pair these concepts with what we know about accessing external APIs and fetching data, we could also create iterators and iterables to modify and perhaps simplify those tasks for us.

Here's a very simple example where we define an async generator function to fetch from the JSONPlaceholder API.

const API_BASE = "https://jsonplaceholder.typicode.com/users/";

async function* fetchUsers() {
  let i = 1;
  while (true) {
    const res = await fetch(`${API_BASE}${i++}`);
    const jsonRes = await res.json();

    if (jsonRes && jsonRes.id) yield jsonRes;
    else return false;
  }
}

const userGen = fetchUsers();

(async () => {
  for await (const user of userGen) {
    console.log(user);
  }
})();

It is very unlikely that we want to loop through a data set of unknown size from an external API. Doing so could have severe negative consequences on the performance of our application. By creating a generator like this, however, we can control exactly how we retrieve the next value from the API.

For example, test this code:

const API_BASE = "https://jsonplaceholder.typicode.com/users/";

async function* fetchUsers() {
  let i = 1;
  while (true) {
    const res = await fetch(`${API_BASE}${i++}`);
    const jsonRes = await res.json();

    if (jsonRes && jsonRes.id) yield jsonRes;
    else return false;
  }
}

const userGen = fetchUsers();

(async () => {
  let getNext = true;
  while (getNext) {
    const res = await userGen.next();
    const user = res.value;
    const done = res.done;

    if (done) {
      alert("Whoops! That was the last user!");
      break;
    }

    getNext = window.confirm(`Here's the current user:

${user.name}
${user.email}
${user.phone}
${user.website}

Press "ok" for the next one, or "cancel" to stop.`);
  }
})();

Using the next() method of iterators, we can choose exactly when we want the next item in the sequence without needing to remember where we left off and without pre-loading all of the user data. We can iterate through an external API of unknown size, and only retrieve the next values when we need them.


Lazy vs. Eager

This method of delaying access to a resource or evaluation of a statement is commonly referred to as "lazy". By contrast, things that happen immediately within the code are called "eager". JavaScript is, by default, an "eager" language, which means each statement in the code is evaluated in its entirety immediately when it is encountered.

To demonstrate this difference, imagine we wanted to create an infinite list of sequential numbers in JavaScript...

// This is a really bad idea... don't do it.
const infiniteList = [];
for (let i = 1; i < Infinity; i++) {
    infiniteList.push(i);
}

Depending on the platform you choose to run this on, it would either result in a complete crash of the platform or some kind of error being thrown.

In lazy languages, creating an infinite list like this is very easy. Instead of trying to fill the entire list immediately (why so eager, JavaScript?), the infinite list's items would only be generated as they are needed.

For instance, here's how we would create an infinite list in Haskell:

infiniteList = [1..]

Very simple. You can even work directly with the infinite list, all the way to infinity!

-- Filter out even numbers
infiniteOdds = filter odd infiniteList

-- Add 3 to each item in the list
infiniteOddsPlusThree = map (+ 3) infiniteOdds

-- Show the first five elements in the console
first5Elements = take 5 infiniteOddsPlusThree
show first5Elements -- "4, 6, 8, 10, 12"

Doing this in JavaScript is not so simple, but iterators and generators allow us to simulate lazy behavior.

Below is how we might accomplish the same lazy list structure in JavaScript by creating a LazyList class. This is a fairly complex implementation which we will walk through the basics of, but if you don't understand the intricacies now, that's okay - you will later.

class LazyList {
  #generator;
  #values = [];
  #done = false;
  #$SKIP = Symbol("skip");

  constructor(genFn) {
    this.#generator = genFn();
  }
  // #next() calls the generator's next() method,
  // and caches values within the #values list.
  next() {
    const { value, done } = this.#generator.next();
    if (done) this.#done = true;
    if (value !== this.#$SKIP) this.#values.push(value);
  }
  // #asGenerator() turns this class instance into
  // a generator itself, yielding each value of
  // the lazy list until the generator has been
  // exhausted. Note that if the generator is infinite,
  // this should not hang, because it is a lazy list.
  asGenerator() {
    function* toGenerator() {
      let i = 0;
      while (true) {
        if (!Reflect.has(this.#values, i)) this.next();
        if (this.#done) return this.#values[i++];

        yield this.#values[i++];
      }
    }
    return toGenerator.apply(this);
  }
  // get() returns the value at index n, but first
  // creates and caches all elements up to index n
  // if those elements do not yet exist (lazy creation).
  get(n) {
    while (this.#values.length <= n && !this.#done) {
      this.next();
    }
    return this.#values[n];
  }
  // take(), map(), and filter() accept a generator and
  // return a generator which performs the desired operation.
  take(n) {
    const takeAid = (n) => (generator) =>
      function* () {
        while (n-- > 0) {
          const { value, done } = generator.next();
          if (done) return value;
          yield value;
        }
      };

    const generator = takeAid(n)(this.asGenerator());
    return new LazyList(generator);
  }
  map(fn) {
    const mapAid = (fn) => (generator) =>
      function* () {
        while (true) {
          const { value, done } = generator.next();
          if (done) return fn(value);
          yield fn(value);
        }
      };

    const generator = mapAid(fn)(this.asGenerator());
    return new LazyList(generator);
  }
  filter(fn) {
    const filterAid = (fn) => (generator) =>
      function* () {
        while (true) {
          const { value, done } = generator.next();
          if (done && fn(value)) return value;
          if (done && !fn(value)) return this.#$SKIP;
          if (!fn(value)) continue;
          yield value;
        }
      };

    const generator = filterAid(fn)(this.asGenerator());
    return new LazyList(generator);
  }
  *[Symbol.iterator]() {
    yield* this.#generator;
  }
}

Now, if we wanted to create an infinite lazy list, we can do so:

const infinite = function* () {
  let i = 1;
  while (true) {
    yield i++;
  }
};

const infiniteList = new LazyList(infinite);
const oddInfiniteList = infiniteList.filter((val) => val % 2 === 1);
const oddInfiniteListPlusThree = oddInfiniteList.map((val) => val + 3);
const firstFiveOddInfiniteListPlusThree = oddInfiniteListPlusThree.take(5);

for (const val of firstFiveOddInfiniteListPlusThree) {
  console.log(val); // 4, 6, 8, 10, 12
}

We can build more complex operations using this lazy behavior as well:

const infiniteList = new LazyList(infinite);
const newList = infiniteList
  .filter((n) => {
    console.log(`Evaluating if ${n} is divisible by both 3 and 5.`);
    return n % 3 == 0 && n % 5 == 0;
  })
  .map((n) => {
    console.log(`Adding 1 to ${n}, then multiplying by 2.`);
    return (n + 1) * 2;
  })
  .take(10);

for (const val of newList) {
  console.log(val); // 32, 62, 92, 122, 152, 182, 212, 242, 272, 302
}

Test this code, and note the console output. Each number in the infinite list is evaluated as it is needed!

In modern JavaScript, much of this functionality is integrated into packages, modules, libraries, and frameworks for us. However, understanding how these things work beneath the surface will allow you to come up with more creative and efficient solutions for your particular design goals.


Experimenting with Iterators and Generators

Let's get some practice building some iterators to a design specification.

ALAB 308H.10.1 - Iterators and Generators will give you two short tasks to accomplish using what you have learned in this lesson.

Copyright © Per Scholas 2024