Iterators, Iterables, and Generators
Learn about JavaScript iterators in this guest post by Francesco Abbruzzese, an author of the MVC Controls Toolkit.
As is the case with C# IEnumerables, JavaScript iterables are also based on the idea of suspending a computation and resuming it when a new value is required. More specifically, iterators and generator functions are the foundation of JavaScript iterables.
Iterators and iterables
Iterators are interfaces (Iterator<T> ) that support a next() operation, which, in turn, returns the following generic interface:
interface IteratorResult<T>
{
done : boolean;
value : T
}
Here the done property must return true if and only if no more values are available in the iteration, and the value property must contain the current element of the iteration. Being an interface, we are free to implement Iterator<T> in the way we prefer. The following is an implementation that lists all integers up to a given value:
function getNumberIterator(x: number): Iterator<number> {
let i = 0;
let iterator = {
next: function (): IteratorResult<number> {
return {
done: i > x,
value: i++
}
}
};
return iterator;
}
let iterator5 = getNumberIterator(5);
The getNumberIterator function returns an iterator that iterates until the value passed in its x parameter. In order to test iterables, we need to add two more declaration libraries to the "lib" TypeScript compiler option, since we are targeting "es5", and not "es6". For the same reason, we need to set the downlevelIteration compiler option to true in order to make that TypeScript compiler translate a for ...of ES6 loop into ES5-equivalent code:
...
"lib": ["dom", "es5",
"es2015.symbol","es2015.symbol.wellknown",
"es2015.generator","es2015.iterable"],
"downlevelIteration": true,
...
The getNumberIterator function snippet must be inserted inside an Iterables namespace into an Iterables.ts file under the .ts folder:
namespace Iterables {
//iterables examples here
}
Then, in order to execute the TypeScript code, replace the previous Scripts section in Views/Home/index.cshtml with the following:
@section Scripts{
<script src="~/js/Iterables.js"></script>
}
Now the iterator5 iterator can be used with a while loop:
let curr: IteratorResult<number>;
while (!(curr = iterator5.next()).done) alert(curr.value);
Typically, however, functions such as getNumberIterator are not used alone, but as building blocks for defining iterables that are the JavaScript equivalent of C# IEnumerables. Iterables are objects that implement the Iterable<T> interface, which, in TypeScript built-in declaration libraries, is defined as follows:
interface Iterable<T> {
[Symbol.iterator](): Iterator<T>;
}
That is, iterables are objects containing a [Symbol.iterator]() method that returns an iterator. It is worth pointing out that Symbol.iterator is a well-known symbol. The previous example may be redefined as follows:
class NumberIterable implements Iterable<number>
{
constructor(readonly x: number) { }
[Symbol.iterator] = () => {
let i = 0;
return {
next: () => {
return {
done: i > this.x,
value: i++
}
}
};
};
}
let iterable5 = new NumberIterable(5);
Iterables may be processed by the for...of loop, which is the TypeScript equivalent of a C# foreach...in loop:
for (let item of iterable5){
alert(item);
}
The whole technique for defining an iterable through the explicit creation of an iterator and its next() method appears quite cumbersome. The definition of the [Symbol.iterator] method is also quite evolved from the simple NumberIterable example that simply iterates over integers.
There are a lot of nested functions and objects; for instance, a function that returns an iterator whose next method returns another object. The next subsection analyzes a technique that simplifies the definition of iterables by avoiding the explicit definition of iterators.
Generator functions and iterables
The source of the whole complexity of the iterator-next-method technique for defining an iterable is the demand to decouple the code of the iterable from the code that uses all the values produced by the iterable. Without this demand, the entire code of the NumberIterable example would collapse into trivial code:
for(let i=0; i<=x; i++) alert(i);
The complication of using a next method is necessary to carry out this code decoupling. The next method call is the way in which producer and consumer of values synchronize, the producer remains in a waiting state until the consumer requires a new value by calling the next method, then it resumes running in order to produce the new value, and then it goes back to a waiting state again.
Notwithstanding the complications associated with the next level iterator, simple examples such as NumberIterable are quite easy to code, but what if you require a more complex enumeration?—For example, an iterable that enumerates all descendants of a DOM node, in other words, the entire subtree of DOM elements that are under a given node.
Processing all the nodes of a tree can be executed by means of a simple recursive procedure, but what about implementing it with the iterator? It would be quite hard because you should transform recursion into iteration and then encode nested iterations with the iterator. This can be quite complex, likelihood of errors.
Luckily, generator functions solve the problem of synchronizing producers and consumers in a smart way. The producer code is written as if the producer and consumer were not decoupled, that is, with loops and/or recursive calls.
However, whenever a new item x is computed, they execute the special instruction yield x. This instruction makes the new value available to the consumer and then it automatically freezes the producer code execution. Execution is resumed when the consumer requires a new item, and continues until the next yieldinstruction is encountered. At that point, the new value is returned to the consumer, and producer execution is frozen again.
With this technique, the core code of the generator function for the NumberIterable example becomes something very simple:
for(let i=0; i<=x; i++) yield i;
This is almost identical to the code needed when there is no producer-consumer decoupling!
A function is declared to be a generator function by appending an asterisk to the function keyword, as can be seen in the following:
function* thisIsAGenerator(....){
...
yield...;
...
}
In case the function keyword is not required, as in the example of class methods, it is sufficient to precede the method definition with an asterisk:
* thisIsAGeneratorMethod(...){
//method code
}
When a generator function/method is invoked, the JavaScript runtime creates an Iterator<T> wrapper around its code and its activation record (the copy of the whole function state that is created each time a function is invoked), and this iterator is returned as the function value.
The Iterator<T> wrapper takes care of resuming and suspending code execution as required, when the consumer code calls the next method of the Iterator<T> wrapper. By way of clarification, let's create a generator function-based implementation of the NumberIterable iterable:
class NumberIterable implements Iterable<number>
{
constructor(readonly x: number) { }
* [Symbol.iterator](){
for (let i = 0; i <= this.x; i++) yield i;
};
}
After this definition, the consumer code may process all the values returned by the iterable in the exact same way as with the previous implementation:
for (let item of new NumberIterable(5)){
alert(item);
}
Generator functions can also use a yield* instruction that, instead of returning a single value, moves the computation path to the values produced by another iterable. The yield* instruction allows the transformation of recursion-based visits into generator functions. Let's see how yield* works with the previously mentioned DOM tree iterable that enumerates the DOM subtree rooted in a given node:
export class DOMTreeIterable implements Iterable<Element>
{
constructor(readonly root: Element) { }
*[Symbol.iterator](): Iterator<Element> {
yield this.root;
for (let child of this.root.children) {
yield* new DOMTreeIterable(child);
};
}
}
DOMTreeIterable returns the root node, and then recalls itself on each child element with yield*. The collection of child elements is iterated with a for ...of.. loop, since all DOM collections are iterables themselves. However, in order to enable TypeScript to accept for ...of.. loops for DOM collections, the "dom.iterable" library must be added to the "lib" compiler option as follows:
"lib": ["dom", "es5",
"es2015.symbol","es2015.symbol.wellknown",
"es2015.generator","es2015.iterable",
"dom.iterable"]
After that, the DOMTreeIterable instance is ready to be tested, for example, by logging the tag names of all the elements contained in the document body in the JavaScript console:
for (let item of new DOMTreeIterable(document.body)) {
console.log(item.tagName);
}
Inheriting from Array<T>
The simplest way to define an iterable is to inherit from a built-in iterable. If a browser supports iterables, then all built-in collections are implemented as iterables. In particular, it is often very useful to inherit from arrays because JavaScript has a lot of built-in operations to process arrays that will be automatically inherited by all array subclasses.
For instance, it is possible to define a subclass of Array<T> that has one more constructor accepting an iterable as its unique argument:
export class EnhancedArray<T> extends Array<T>
{
constructor(x: number);
constructor(...items: T[])
constructor(x: Iterable<T>);
constructor(x?: number | Array<T> | Iterable<T>) {
if (typeof x === "undefined") super();
else if (x instanceof Array) super(...x);
else if (typeof x == "number") super(x)
else {
super();
for (let item of x) this.push(item);
}
}
}
The EnhancedArray<T> subclass provides the same two standard constructors of Array<T> and then adds the new one. The elements of the iterable passed as arguments are pushed to the subclass one after the other.
Subclasses of Array<T> may define the [Symbol.isConcatSpreadable] computed Boolean property. If it returns true, the elements of any instance of the subclass are flattened with all elements of other arrays when the subclass is involved in an array concat operation.
If [Symbol.isConcatSpreadable] returns false, the entire subclass is considered a single non-array element and its elements are not flattened during array concatoperations. Thus, for instance, if you add the following code to the EnhancedArray<T> class, then instances of EnhancedArray<T> will never have their elements flattened in array concat operations:
...
get [Symbol.isConcatSpreadable]() {
return false;
}
...
The next subsection describes new collections introduced by ECMAScript 2015.
ECMAScript 2015 built-in iterables
ECMASCript 2015 has built-in iterables that implement the abstract dictionaries and set data structures. In order to use them in TypeScript, the "es2015.collection" declarations library must be added to the "lib" compiler option:
"lib": ["dom", "es5",
"es2015.symbol","es2015.symbol.wellknown",
"es2015.generator","es2015.iterable",
"dom.iterable", "es2015.collection"]
Built-in iterables are supported by all mainstream browsers with the exception of Internet Explorer (just Internet Explorer, not Edge), which offers partial support for Map, Set, and WeakMap, and doesn't support WeakSet at all.
Partial support refers to the absence of all iterable-related features, since, as has already been pointed out, Internet Explorer doesn't support iterables. All built-in iterables have a constructor that either accepts no argument, an array, or an iterable (Internet Explorer only accepts an array).
In the case of Set and WeakSet, the iterable contains all the elements to insert initially into the Set (WeakSet), while, in the case of Map and WeakMap, the iterable is composed of two-element tuples whose first element is the dictionary key and whose second element is the corresponding value.
A review of each ECMAScript 2015 built-in iterable follows. As regards the examples used in this subsection, please create a new TypeScript file named BuiltInIterables.ts under the .ts folder.
Map<K, V> and WeakMap<K, V>
Map<K, V> is a key-value pair dictionary. For example, you may use it to create a book of friends that associates a Person object with each friend's name that represents them and contains all their data:
namespace BuiltInIterables {
import Person = SymbolExample.Person;
let friendBook = new Map<string, Person>();
}
New key-value pairs are added using the set method:
friendBook.set("John", new Person("John", "Smith"));
Values are then retrieved through their associated keys using the get method:
let found = friendBook.get("John");
if (typeof found !== "undefined")
alert(found.name + " " + found.surname);
The size property returns the number of key-value pairs stored in Map:
alert(friendBook.size);
The forEach method invokes a callback on each pair contained in Map:
friendBook
.forEach((value, key, dict) =>
{ alert(value.surname) })
The callback is passed, along with the value, the key, and the whole Map.
The delete method deletes a pair from Map through its key:
friendBook
.delete("John")
alert(friendBook.size);
The clear method deletes all pairs (though it is, usually, more efficient to create a new empty Map). The entries property contains an iterable with all key-value pairs represented as two-element tuples. The keysproperty contains an iterable that enumerates all keys, while the values property contains an iterable that enumerates all values.
WeakMap<K, V> works as Map<K, V>, the only difference being the manner in which the key-value pairs are garbage-collected by JavaScript (garbage collection is the process that removes all unused objects to free up memory).
More specifically, if during the evolution of the process, a key of a key-value pair is used just by a WeakMap instance, while no other object has a pointer to it, then the whole key-value pair is removed from that WeakMap instance. This way, the value referenced in the key-value pair remains completely unreferenced and is garbage collected by JavaScript.In other words, the references of all WeakMaps to all their key objects are not taken into account by the garbage-collector in deciding whether an object is used or not.
WeakMaps are useful for encoding temporary associations between objects used in a computation, so that when that computation ends and some of those objects are no longer used, they must also be removed from all the maps they are in so that the garbage collector may free up their memory.
Set<T> and WeakSet<T>
Set<T> is an implementation of a mathematical finite set. Accordingly, it is a collection with no repetitions, so if the same value is added several times, only the first occurrence is taken.
Values are added using the add method:
let mySet = new Set<number>([1, 5, 7, 9]);
mySet.add(10);
The has Boolean method tests whether a value is contained in Set:
alert(mySet.has(10));//it returns true;
alert(mySet.has(9));//it returns true;
alert(mySet.has(8));//it returns false;
The size property returns the number of values contained in Set:
alert(mySet.size);//it returns 5;
The forEach method invokes a callback on each value contained in Set:
mySet.forEach((value) => {
alert(value)
});
A value may be removed from a set using the delete method:
mySet.delete(9);
alert(mySet.has(9));//it returns false;
The clear method deletes all values from a set (though it is, usually, more efficient to create a new empty set). Finally the values property contains an iterable that enumerates all values.
The difference between WeakSet<T> and Set<T> is the same as the difference between WeakMap<K, V> and Map<K, V>. That is, if, during the process evolution, a value is used just by WeakSet instances, while no other object has a pointer to it, that value is removed from that WeakSet so that it remains completely unused and may be garbage-collected by the JavaScript garbage collector.
Hope you enjoyed reading this article. If you want to learn more about C# and TypeScript, you must check out Hands-On TypeScript for C# and .NET Core Developers. Writing clean, object-oriented code in JavaScript gets trickier and complex as the size of the project grows. This is where Typescript comes into the picture; it lets you write pure object-oriented code with ease, giving it the upper hand over JavaScript. Hands-On TypeScript for C# and .NET Core Developers introduces you to basic TypeScript concepts by gradually modifying standard JavaScript code