Iteration is a standard that connects operations with data containers: Each operation that follows this standard, can be applied to each data container that implements this standard.
In this blog post:
.map()
, .filter()
, and .forEach()
.Iteration was added to JavaScript in ECMAScript 6. There are two sides to this protocol (interfaces and rules for using them):
A data producer that implements the iteration protocol is called an iterable. That term is also used as an adjective: “an iterable data structure”.
A key benefit of iteration is that each data consumer that uses iteration, can be used with each iterable data producer.
The JavaScript standard library already has several iteration-based data producers and data consumers – for example:
array.keys()
(iterable objects that are not Arrays)map.entries()
(iterable objects that are not Arrays)for-of
Array.from()
[...input]
)func(...input)
)Alas, JavaScript does not yet support many iteration-based algorithms. These are three examples of helper functions that would be useful:
map
: lists the results of invoking a callback on each value of an iterable.filter
: lists all values of an iterable for which a callback returns true
.forEach
: invokes a callback with each value of an iterable.Both input and output of map
and filter
are iterable, which means that we can chain these operations.
The two most important entities in the iteration protocol are:
An object obj
becomes iterable by implementing one method:
obj[Symbol.iterator]()
: This method return iterators.An iterator iter
is an object that delivers values via one method:
iter.next()
: This method returns objects with two properties:
.value
: contains the current value.done
: is false
as long as there still are values and true
afterwards.This is what using iteration looks like in practice:
> const iterable = ['a', 'b'];
> const iterator = iterable[Symbol.iterator]();
> iterator.next()
{ value: 'a', done: false }
> iterator.next()
{ value: 'b', done: false }
> iterator.next()
{ value: undefined, done: true }
When implementing an iterable, a common technique is to make that iterable also an iterator:
function iterArgs(...args) {
let index = 0;
const iterable = {
[Symbol.iterator]() {
return this; // (A)
},
next() {
if (index >= args.length) {
return {done: true};
}
const value = args[index];
index++;
return {value, done: false};
}
};
return iterable;
}
const iterable1 = iterArgs('a', 'b', 'c');
assert.deepEqual([...iterable1], ['a', 'b', 'c']);
In line A, we don’t return a new object, we return this
.
This technique has three upsides:
We’ll first examine upside #2 and then upside #3.
In line B in the following code, we can continue the iteration that we started in line A.
const iterable2 = iterArgs('a', 'b', 'c');
const iterator2 = iterable2[Symbol.iterator]();
const firstItem = iterator2.next().value; // (A)
assert.equal(firstItem, 'a');
const remainingItems = [...iterator2]; // (B)
assert.deepEqual(
remainingItems, ['b', 'c']);
All iterators created by the JavaScript standard library are iterable. The objects returned by generators are also both iterators and iterables.
Therefore, we can use generators to implement iterables:
function* iterArgs(...args) {
for (const arg of args) {
yield arg;
}
}
const iterable = iterArgs('red', 'green', 'blue');
assert.deepEqual(
Array.from(iterable),
['red', 'green', 'blue']
);
But we can also use them to implement iterators (line A):
class ValueContainer {
#values;
constructor(...values) {
this.#values = values;
}
* [Symbol.iterator]() { // (A)
for (const value of this.#values) {
yield value;
}
}
}
const iterable = new ValueContainer(1, 2, 3);
assert.deepEqual(
Array.from(iterable),
[1, 2, 3]
);
With iterable iterators, we now have two kinds of iterators.
On one hand, there are iterables over which we can iterate as often as we want:
function iterateTwice(iterable) {
return [...iterable, ...iterable];
}
const iterable1 = ['a', 'b'];
assert.deepEqual(
iterateTwice(iterable1),
['a', 'b', 'a', 'b']);
On the other hand, there are iterables over which we can only iterate once:
// .values() returns an iterable (not an Array like Object.values())
const iterable2 = ['a', 'b'].values();
assert.deepEqual(
iterateTwice(iterable2),
['a', 'b']);
function* gen() {
yield 'a';
yield 'b';
}
const iterable3 = gen();
assert.deepEqual(
iterateTwice(iterable3),
['a', 'b']);
Conceptually, things have become more confusing:
for-of
, spreading, etc. only accept iterables.array.keys()
, and map.entries()
return iterators that just happen to also be iterable.%IteratorPrototype%
: the prototype of all iterators in the standard library In the ECMAScript specification, internal objects are enclosed in percent signs. One such object is %IteratorPrototype%
:
// We omit the percent signs so that it’s legal JavaScript
const IteratorPrototype = {
[Symbol.iterator]() {
return this;
},
};
This method is inherited by all objects that have %IteratorPrototype%
as a prototype and makes them iterable – if this
is also an iterator.
Even though %IteratorPrototype%
is not directly accessible from JavaScript, we can access it indirectly:
const IteratorPrototype = Object.getPrototypeOf(
Object.getPrototypeOf(
[][Symbol.iterator]()
)
);
%IteratorPrototype%
is in the prototype chain of all iterators that are created by the standard library:
> IteratorPrototype.isPrototypeOf('abc'[Symbol.iterator]())
true
> IteratorPrototype.isPrototypeOf([].keys())
true
> IteratorPrototype.isPrototypeOf(new Map().entries())
true
> IteratorPrototype.isPrototypeOf((function* () {})())
true
> IteratorPrototype.isPrototypeOf('aaa'.matchAll(/a/g))
true
One of the proposals for iteration helpers depends on the fact that %IteratorPrototype%
is a prototype of many iterators. We’ll get into the details when we look at that proposal.
If we want to be able to method-chain iteration helpers like we can with Arrays, the conceptually cleanest way is to make those helpers methods of iterable objects. That could look as follows.
class Iterable {
* map(mapFn) {
for (const item of this) {
yield mapFn(item);
}
}
* filter(filterFn) {
for (const item of this) {
if (filterFn(item)) {
yield item;
}
}
}
toArray() {
return [...this];
}
}
class Set2 extends Iterable {
#elements;
constructor(elements) {
super();
// The real Set eliminates duplicates here
this.#elements = elements;
}
[Symbol.iterator]() {
return this.#elements[Symbol.iterator]();
}
// ···
}
Now we can do:
const arr = new Set2([0, -1, 3, -4, 8])
.filter(x => x >= 0)
.map(x => x * 2)
.toArray()
;
assert.deepEqual(
arr, [0, 6, 16]
);
If we want our helpers to be methods, then iterables are the right location for them. Apart from chaining, another benefit of methods is that specific classes can override a default implementation of an operation if they can implement it more efficiently (via the specific features of the class).
Alas, we are facing a fatal obstacle: We can’t change the inheritance hierarchies of existing classes (especially not of Array
). That makes it impossible to use this approach.
Another way of enabling method chains is via a technique that became popular in the JavaScript world via the libraries jQuery and Underscore: We wrap the objects that we want to operate on and add methods to them that way:
function iter(data) {
return {
filter(filterFn) {
function* internalFilter(data) {
for (const item of data) {
if (filterFn(item)) {
yield item;
}
}
}
return iter(internalFilter(data));
},
map(mapFn) {
function* internalMap(data) {
for (const item of data) {
yield mapFn(item);
}
}
return iter(internalMap(data));
},
toArray() {
return [...data];
},
};
}
const arr = iter(new Set([0, -1, 3, -4, 8]))
.filter(x => x >= 0)
.map(x => x * 2)
.toArray()
;
assert.deepEqual(
arr, [0, 6, 16]
);
Yet another way of getting method chaining is by adding helper methods to iterators. There is an ECMAScript language proposal for this approach.
How does that work? As we have seen, all iterators created by the standard library already have the object %IteratorPrototype%
in their prototype chains. We can complete this prototype into a full class:
const IteratorPrototype = Object.getPrototypeOf(
Object.getPrototypeOf(
[][Symbol.iterator]()
)
);
// “Class” based on IteratorPrototype
function Iterator() {}
Iterator.prototype = IteratorPrototype;
Iterator.prototype.filter = function* (filterFn) {
for (const item of this) {
if (filterFn(item)) {
yield item;
}
}
};
Iterator.prototype.map = function* (mapFn) {
for (const item of this) {
yield mapFn(item);
}
};
Iterator.prototype.toArray = function () {
return [...this];
};
Interestingly, due to how instanceof
works and due to Iterator.prototype
being a prototype of each iterator in the standard library, many objects are already instances of Iterator
:
> 'abc'[Symbol.iterator]() instanceof Iterator
true
> [].values() instanceof Iterator
true
> new Map().entries() instanceof Iterator
true
> (function* () {})() instanceof Iterator
true
> 'aaa'.matchAll(/a/g) instanceof Iterator
true
This is what using the new approach looks like:
const arr = new Set([0, -1, 3, -4, 8])
.values() // get iterator
.filter(x => x >= 0)
.map(x => x * 2)
.toArray()
;
assert.deepEqual(
arr, [0, 6, 16]
);
With this approach, we have to distinguish three kinds of iterables:
Object.keys()
, etc.)Iterator
(array.keys()
, map.entries()
, etc.)Iterator
(in existing code).The proposal provides the tool function Iterator.from()
to handle all these cases in the same manner:
Iterator
, it returns it as is.Iterator
, it wraps that iterable so that it has the methods of Iterator
.Iterator
is a significant change of the original iteration protocol.
Iterator
, and iterable iterators that don’t extend Iterator
.
Iterator.from()
, but then we get an API that is like the wrapping approach.Iterator.from()
: It converts an iterable to an iterator, then we invoke iterator methods, then we use a construct such as for-of
to process the result. That construct only accepts iterables, but instances of Iterator
also happen to be iterable.zip()
), these operands would be iterables, while this
would be an instance of Iterator
.Iterator
and would probably be functions.The established way of providing helpers for iterables is actually not via methods but via functions. Examples include Python’s itertools and JavaScript’s Underscore/Lodash.
The library @rauschma/iterable
prototypes what that would look like. It is implemented roughly like this:
const Iterable = {
* filter(filterFn, iterable) {
for (const item of iterable) {
if (filterFn(item)) {
yield item;
}
}
},
* map(mapFn, iterable) {
for (const item of iterable) {
yield mapFn(item);
}
},
toArray(iterable) {
return [...iterable];
},
// ···
};
const {filter, map, toArray} = Iterable;
const set = new Set([0, -1, 3, -4, 8]);
const filtered = filter(x => x >= 0, set);
const mapped = map(x => x * 2, filtered);
const arr = toArray(mapped);
assert.deepEqual(
arr, [0, 6, 16]
);
Note that Iterable
isn’t really an object but a namespace/pseudo-module for the functions, similar to JSON
and Math
.
Should JavaScript get a pipeline operator, we could even use these functions as if they were methods:
const {filter, map, toArray} = Iterable;
const arr = new Set([0, -1, 3, -4, 8])
|> filter(x => x >= 0, ?)
|> map(x => x * 2, ?)
|> toArray(?)
;
range(start, end)
) will be important additions to this category.Functions won’t allow method chaining. However:
If we are not chaining, functions are convenient:
const filtered = filter(x => x, iterable);
In contrast, this is what using iterator methods looks like:
const filtered1 = iterable.values().filter(x => x);
const filtered2 = Iterator.from(iterable).filter(x => x);
In this blog post, we have only seen synchronous iteration: We immediately get a new item when we request it from an iterator.
But there is also asynchronous iteration where code pauses until the next item is available.
One important use case for asynchronous iteration is processing streams of data (e.g. web streams and Node.js streams).
Even if we apply multiple operations to an asynchronous iterable, the input data is processed one item at a time. That enables us to work with very large datasets because we don’t have to keep all of them in memory. And we see output much more quickly (compared to first applying the first operation to the complete dataset, then the second operation to the result, etc.).
We have explored iteration and four approaches for implementing iteration helpers:
I expect (at most) one of these approaches to be added to JavaScript. How should we choose?
Given all the constraints we are facing, my favorite is (4):
JavaScript may eventually get a pipeline operator. That would even enable us to chain functions. But the pipeline operator is not required to make functions an appealing solution (details).
If methods are preferred over functions, I’d argue in favor of wrapping (as done by jQuery and supported by Underscore/Lodash). Compare:
// Iterator methods
const arr1 = new Set([0, -1, 3, -4, 8])
.values() // get iterator
.filter(x => x >= 0)
.map(x => x * 2)
.toArray()
;
// Wrapping
const arr2 = iter(new Set([0, -1, 3, -4, 8]))
.filter(x => x >= 0)
.map(x => x * 2)
.toArray()
;
Using global variables as namespaces for functions is a common pattern in JavaScript. Examples include:
Math
JSON
Reflect
Temporal
There is a proposal for built-in modules in JavaScript (i.e., a module-based standard library). Built-in modules would provide functionality such as what is listed above and could also contain function-based iteration helpers:
import {map, filter, toArray} from 'std:Iterable';
Chapters in my book “JavaScript for impatient programmers” (which is free to read online):