Series: JavaScript Iterators and Generators
Introduction Link to heading
The first thing to point out is that iteration in JavaScript is based on a protocol: a set of conventions that replace what would have been interfaces in a language with support for interfaces. Anyway, the ECMAScript Specification mostly uses the word “interface”, therefore I will do the same.
To whom this concept may be new, you should imagine interfaces as contracts between two entities in your code. Without the contract, these two parts would know each other too much, becoming too dependent on each other: a change inside one would probably force us to change the other.
Going back to iterators, their main purpose is to allow the use of each element of a given collection. They are so good that the consumer doesn’t need to know how the collection stores and manages those elements. As long as the iterator interface(s) is respected, the consumer and the collection remain completely independents: we will be able to change the internal details of the collection without affecting the consumer. In fact, we could replace the entire collection with another one. At the same time, the collection does know nothing about the consumer. Therefore it can be iterated by consumers also very different from each other.
Please, respect the contract.
The Iterable, the Iterator and the IteratorResult interfaces Link to heading
There are three interfaces on which the whole iteration thing is based.
The Iterable Link to heading
The Iterable interface defines what an entity has to implement to be considered an iterable. The specification says that an iterable has a required method, the @@iterator method, which returns an object that implements the Iterator interface. What is @@iterator? Is a specific Symbol that we can find into the Symbol constructor: Symbol.iterator.
const Iterable = {
[Symbol.iterator]() {
return Iterator;
}
}
The Iterator Link to heading
The Iterator interface defines what an entity has to implement to be considered an iterator. The specification says that an iterator has a required method: the next method. This method, that is the fulcrum of the iteration itself, returns an object that implements the IteratorResult interface. Its main purpose is to get the subsequent element from the collection until there are no more entries.
There are two other optional methods: the return method and the throw method. If they return a value, it must be an IteratorResult. The purpose of the former is to signal to the iterator that the consumer is not going to call the next method anymore, even if the iteration has not reached its end. In this way, the iterator will be able to perform any cleanup it may need to do. The purpose of the latter is to signal to the iterator that the consumer has encountered an error.
All three methods accept at least one argument:
- the next method should be able to receive one or more arguments, but as the specification says “their interpretation and validity is dependent upon the target iterator”
- the return method should return back the received argument, inserting it into the returned IteratorResult
- the throw method should throw the received argument, which usually is an exception
Remember to check the existence of the last two methods before calling them!
const Iterator = {
next() {
return IteratorResult;
},
return() {
return IteratorResult;
},
throw(e) {
throw e;
}
}
The IteratorResult Link to heading
The IteratorResult interface defines what an entity has to implement to be considered a valid result of a generic iteration step.
The specification says that an iterator result has two fields, both surprisingly optional: the done field and the value field. The done field is a boolean flag that signals the ends of an iteration. It should be false as long as the values returned by the iterator are valid, to then become true after the last valid value is returned. If the done flag is omitted, it is considered to have the value false. The value field can contain any valid ECMAScript value. It is the current iteration value of each iteration step until the done flag become true. After that, this is the return value of the iterator, if it supplied one. If the value field is omitted, it is considered to have the value undefined.
const IteratorResult = {
value: any,
done: boolean,
}
Conventions Link to heading
There are some general conventions that should be followed to create well-formed iterators:
- Each Iterable entity should return a fresh, new iterator each time the @@iterator method is called.
- Each Iterator entity should be an Iterable too (more on that later), implementing the @@iterator method with a function that simply returns this, that is a reference to the iterator itself. This is a controlled exception of the previous rule.
- Explicitly report each iteration step’s valid value with a done flag set to false. Do not combine relevant values with
done:true. - If the return method or the throw method are called, the iterator should be considered exhausted and any subsequent invocations of the next method should no more return any valid value.
Anyway, if the current return/throw call returns a value, it should be combined with
done: true. - After the last value was returned, the next method should return
{ value: undefined, done: true }. Do not throw errors. Simply signal the end of the iteration as indicated, even if the next method is called several times after that.
Default iterators Link to heading
Let’s see how to use one of the most common iterators already present in the language. Because arrays implement the @@iterator method by default, getting an iterator to iterate over an array is pretty straightforward:
const array = [1, 2, 3];
// get a fresh, new iterator to iterate over the array
const iterator = array[Symbol.iterator]();
Now let’s use it:
// remember: we have to call the 'next' method to iterate
iterator.next(); // { value: 1, done: false }
iterator.next(); // { value: 2, done: false }
iterator.next(); // { value: 3, done: false }
iterator.next(); // { value: undefined, done: true }
iterator.next(); // { value: undefined, done: true }
You can see how some of the conventions we talked about earlier are respected:
- the last valid value (
3) is coupled with adone:false, not adone:true - I intentionally went out of bounds to show you that no errors were thrown. Instead we are always getting back
{ value: undefined, done: true }
Arrays are not the only built-in iterables: String objects, TypedArrays, Maps and Sets are iterables too, because each of their prototype objects implements the @@iterator method.
Using iterators Link to heading
Let’s create a function that takes an iterable and a callback, passing to the latter each iterator result’s value:
function iterateOver(iterable, cb) {
// let it throw if the iterable argument is not an iterable
const iterator = iterable[Symbol.iterator]();
// it will contains the iterator result of each step
let iteratorResult;
// starts the iteration
iteratorResult = iterator.next();
// do the while loop only for values coupled with 'done:false'
while(!iteratorResult.done) {
// pass to the callback the value of each step
cb(iteratorResult.value);
// move forward the iterator
iteratorResult = iterator.next();
};
// before returning, let the iterator do some cleanup
iterator.return && iterator.return();
}
Follow an example of its use:
iterateOver([1,2,3], console.log); // 1, 2, 3
The for-of loop Link to heading
Luckily we don’t need to write such type of function: the JavaScript provides to us a dedicated syntax: the for-of loop.
Its logic could be summarized in the following points:
- Call the @@iterator method of the iterable.
- Call the next method of the received iterator with no arguments.
- Check if the
doneflag of the just received iterator result is set to true; if so, jump to point number 5. Otherwise, continue. - Provide to the client the value contained into the iterator result, then jump to point number 2.
- Discard the iterator result and call the return method of the iterator with no arguments, if the method is present.
for(const value of [1,2,3]) {
console.log(value); // 1, 2, 3
}
Array destructuring and the array spread operator Link to heading
Behind instructions like const [a, b] = iterable; and const clone = [...iterable] lies the same mechanism: an iterator is get from the iterable to be usually used only partially with array destructuring, but until it is exausted with the array spread operator.
Custom iterators Link to heading
Let’s finally see two custom implementations of the three interfaces we have discussed above: an iterator for a collection and an iterator for a producer.
Collection Link to heading
The following simple collection store all the names of the user that have joined a particular telegram group. The boolean flag indicates whether a user is an administrator of the group:
const users = {
james: false,
andrew: true,
alexander: false,
daisy: false,
luke: false,
clare: true,
}
Now, let’s create an iterator that returns only the administrators' names.
The first thing to do is to make the users collection an iterable, adding the @@iterator method to it:
const users = {
// ...users
[Symbol.iterator]() {
// each call will return a new iterator
const iterator = {
next() {
// we set the iterator skeleton
// adding only an almost empty 'next' method, for now
return { done: true };
}
}
return iterator;
}
}
If you think about it, we have just met all the requirements needed to properly implement, from the ECMAScript perspective, the iterators interfaces.
Obviously, the result is far away from what we really need. And we are not even respecting the aforementioned conventions.
But, just to let you know, users is now a full-fledged iterable and could be used safely not only with the for-of loop, but also with array destructuring and the array spread operator.
Enough fun for now, let’s add the logic we need. The second thing to do is to get an array with the object’s keys, that we are going to iterate with an index. Both the array of keys and the index must be unique for each generated iterator, so they will be created during the call to the @@iterator method:
const users = {
// ...users
[Symbol.iterator]() {
// here the relevant parts
const keys = Object.keys(this);
let index = 0;
const iterator = {
next() {
return { done: true };
}
}
return iterator;
}
}
At each iteration step, we have to advance one or more position inside the keys array, skipping those that don’t match with a true boolean flag inside the users collection.
Is noteworthy that I’ve changed the next method signature, turning it into an arrow function to preserve the this context:
const users = {
// ...users
[Symbol.iterator]() {
const keys = Object.keys(this);
let index = 0;
const iterator = {
// here the relevant parts
next: () => {
// this === 'users'
// skip all the normal users '!this[keys[index]]'
// stop if we ran out of users 'index < keys.length'
while (
!this[keys[index]] &&
index < keys.length
) { index++; }
return { done: true };
}
}
return iterator;
}
}
Do not be scared by !this[keys[index]].
Remember that keys is an array with the users object’s keys, therefore an array containing the telegram group users' names. Thus, keys[index] will return the key, the name of a user, at the given index. After that, this[key] will simply return true or false depending on the user status.
Now let’s focus on the iterator result that we have set to { done: true } for convenience.
If you are asking, we could have returned an empty object {} and the IteratorResult interface would have been respected anyway. However, don’t forget that a missing done flag means done:false. Therefore, if you had tried to use the users object inside a for-of loop, for example, you would have stuck your browser because the for-of would never have ended.
To properly set the done flag, we can check if we have exceeded the numbers of keys thanks to the length property of the keys array.
To set each returned value, since we want the administrators' names, we can simply get the name corresponding to the current index:
const users = {
// ...users
[Symbol.iterator]() {
const keys = Object.keys(this);
let index = 0;
const iterator = {
next: () => {
while (!this[keys[index]] && index < keys.length) index++;
// here the relevant part
return {
done: index >= keys.length,
// after reading the name corresponding to the current index,
// do not forget to move forward the 'index'
// for the next iteration
value: keys[index++],
};
}
}
return iterator;
}
}
That’s it!
Let’s try to use it:
[...users].forEach(name => console.log(name));
// andrew, clare
A necessary digression Link to heading
Let’s take an array:
const array = [1, 2, 3];
and feed a for-of loop with it:
for (const n of array) {
console.log(n);
}
We already know the output:
// first iteration: 1
// second iteration: 2
// third iteration: 3
What about that:
const iterator = array[Symbol.iterator]();
// we no more provide to the 'for-of' loop the array
// but we provide an iterator of the array
for (const n of iterator) {
console.log(n);
}
What do you expect? An exception? Wrong! The outcome will be exactly the same:
// first iteration: 1
// second iteration: 2
// third iteration: 3
Let's try the same with our custom iterable:
```js
const userIterator = users[Symbol.iterator]();for (const name of userIterator) { console.log(name); }
What do you expect? The same output as before (I mean `andrew, clare`)? Wrong!
You'll get an exception: `TypeError: userIterator is not iterable`.
Of course, `userIterator` is not an __iterable__, it is an __iterator__! But wait a moment, why doesn't it make any fuss with the `array` iterator? What's the difference?
The truth is that default iterators, like the `array` one, are both an __iterator__ and an __iterable__. But what in the world should mean iterating over an iterator?
Inception.
Don't worry. We'll return soon to this point, to finally explain the convention number __2__.
### Producer
Another place where iterators shine is the __producers__ land.
A producer is a stateful function which return values depend on the previous returned ones. A classic example is a function that returns the next number of the Fibonacci series, starting from __0__. Let's try to code it:
```js
const fibonacciProducer = (function IIFE() {
// here we store the state
let previousValue = 1; // for convenience
let currentValue = 0;
// here it is: a closure
return function realFibonacciProducer() {
// clone the currentValue
const valueToBeReturned = currentValue;
// calculate the next value
const nextValue = previousValue + currentValue;
// update the state
previousValue = currentValue;
currentValue = nextValue;
// return the correct value
return valueToBeReturned;
}
})();
Here it is what happens if you call fibonacciProducer:
fibonacciProducer(); // 0
fibonacciProducer(); // 1
fibonacciProducer(); // 1
fibonacciProducer(); // 2
fibonacciProducer(); // 3
fibonacciProducer(); // 5
fibonacciProducer(); // 8
fibonacciProducer(); // 13
// ...
There is nothing wrong with this implementation, apart from a missing integers owerflow check, but we can improve it adding iterators to let it be usable with all the ES6 features that plays well with iterables, like for-of loops.
Let’s do it:
const fibonacciProducer = (function IIFE() {
// enhanced version of the previous 'realFibonacciProducer'
function updateState({previousValue, currentValue}) {
// calculate the next value
const nextValue = previousValue + currentValue;
// new values to update the state
const newPreviousValue = currentValue;
const newCurrentValue = nextValue;
// return the new values
return {
newPreviousValue,
newCurrentValue
};
}
// 'fibonacciProducer' will be an iterators factory
return function iteratorFactory() {
// each iterator will have its own state
let previousValue = 1; // for convenience
let currentValue = 0;
const iterator = {
next: () => {
// integers owerflow check
const outOfRange = currentValue > Number.MAX_SAFE_INTEGER;
const iteratorResult = {
done: outOfRange,
value: outOfRange ? void 0 : currentValue,
}
if(!outOfRange) {
// update the current state
const newState = updateState({previousValue, currentValue});
currentValue = newState.newCurrentValue;
previousValue = newState.newPreviousValue;
}
return iteratorResult;
}
}
return iterator;
}
})();
Here’s how to use the enhanced fibonacciProducer:
// request an iterator
const fibonacciIterator = fibonacciProducer();
// use it!
fibonacciIterator.next() // { done: false, value: 0 }
fibonacciIterator.next() // { done: false, value: 1 }
fibonacciIterator.next() // { done: false, value: 1 }
fibonacciIterator.next() // { done: false, value: 2 }
fibonacciIterator.next() // { done: false, value: 3 }
fibonacciIterator.next() // { done: false, value: 5 }
fibonacciIterator.next() // { done: false, value: 8 }
fibonacciIterator.next() // { done: false, value: 13 }
// ...
Thanks to the iterator interface we also got the possibility to restart the the production of values out of the box: it is sufficient to request another iterator!
The IterableIterator pattern Link to heading
Unfortunately, the following code continues to throw an exception:
const fibonacciIterator = fibonacciProducer();
for (const value of fibonacciIterator) {
console.log(value);
}
because fibonacciIterator is an iterator but not an iterable.
Pay attention to this fact: there is not a collection into play to be given directly to the for-of loop as we could do with the previous array.
We can only get iterators from fibonacciProducer.
This is an expected but also a wanted boundary to help you understand the IterableIterator pattern.
In fact, it may happen that we have to handle an iterator disconnected from any collection, as in the producer case, or derived from a collection that we cannot directly reach. We could have created an iterator from a collection and we have provided only the iterator to a function: the subroutine won’t be able to directly use the collection. Another example: the collection is a private member of a class, therefore not directly accessible. However, the class provides a method that returns an iterator for that collection.
If we want to be able to use the ES6 features written for iterables with those types of iterators, we have to force them to be iterables too.
- How? The iterator should return itself if used like an iterable:
const Iterator = {
next() {
return IteratorResult;
},
[Symbol.iterator]() {
return this;
}
}
- What’s the meaning of that? Remember what utilities like the
for-ofloop do: they call the @@iterator method to get an iterator from an iterable. If the entity to which the iterator is requested is itself an iterator, it should simply return itself!
Don’t consider this point as a special case that can be forgotten. All the iterables present by default in the language provide iterators defined with this characteristic. All the iterators that you can get with any language feature, like generators, follow this convention. Therefore is a good idea to always implement iterators that are also iterables, even because is unlikely you know beforehand how the collections and iterators you create will be used.
Conclusion Link to heading
We are at the end of the first article about Iterators and Generators.
We have learnt why the iterator pattern is so important, how JavaScript wants us to implement the three interfaces (Iterable, Iterator, IteratorResult) and some useful conventions which we should adhere to. Then we have seen an example of a default iterator provided by the language, how to use it with the most common ES6 feature and what should be done to create iterators that could be used which such features. We also have analyzed in detail how to define custom iterables for both a custom collection and a producer.
Next article will focus on Generators, a nice ES6 feature that could be used to create iterators and to do a lot of interesting stuff!
I hope to see you there again 🙂 and on twitter!
Acknowledgements Link to heading
I would like to thank Nicolò Maria Mezzopera for helping me identify a lot of grammatical errors. If you are a Vue.js developer, you need to check out his next workshop: vueandme. I also wish to thank Gabriele Di Simone, Marco Terzolo and Giovanni Riga for the time they’ve spent to check the article.
Bibliography Link to heading
- ECMAScript 2019 specification
- You Don’t Know JS series by Kyle Simpson
- Exploring JS series by Dr. Axel Rauschmayer