Handling each item in a collection is a very common operation. JavaScript provides many ways to iterate over a collection, from simple for and for each loop to map(), filter() and array comprehensions (array derivation). In JavaScript 1.7, iterators and generators bring new iterative mechanisms in the core JavaScript syntax, and also provide mechanisms to customize the behavior of for…in and for each loops.
Iterator
An iterator is an object that accesses an element in a collection sequence every time and tracks the current position of iterations in that sequence. In JavaScript iterator is an object that provides a next() method, which returns the next element in the sequence. This method throws a StopIteration exception when all elements in the sequence are traversed.
Once the iterator object is created, it can be called implicitly by explicitly repeating next(), or by using JavaScript's for…in and for each loop.
A simple iterator that iterates over objects and arrays can be created using Iterator():
The code copy is as follows:
var lang = { name: 'JavaScript', birthdayYear: 1995 };
var it = Iterator(lang);
Once initialization is complete, the next() method can be called to access the object's key-value pairs in turn:
The code copy is as follows:
var pair = it.next(); //Key-value pairs are ["name", "JavaScript"]
pair = it.next(); //The key-value pair is ["birthday", 1995]
pair = it.next(); //A `StopIteration` exception was thrown
The for…in loop can be used to replace the explicit call to the next() method. When the StopIteration exception is thrown, the loop will automatically terminate.
The code copy is as follows:
var it = Iterator(lang);
for (var pair in it)
print(pair); //One [key, value] key-value pair in it is output each time
If you only want to iterate over the key value of the object, you can pass the second parameter into the Iterator() function, with the value true:
The code copy is as follows:
var it = Iterator(lang, true);
for (var key in it)
print(key); //Only output key value
One advantage of using Iterator() to access objects is that custom properties added to Object.prototype are not included in the sequence object.
Iterator() can also be used on an array:
The code copy is as follows:
var langs = ['JavaScript', 'Python', 'Haskell'];
var it = Iterator(langs);
for (var pair in it)
print(pair); //Only iteration output [index, language] key-value pair
Just like traversing an object, the result of passing true into the traversal as a second parameter will be the array index:
The code copy is as follows:
var langs = ['JavaScript', 'Python', 'Haskell'];
var it = Iterator(langs, true);
for (var i in it)
print(i); //Output 0, then 1, then 2
Use the let keyword to assign indexes and values to block variables separately within the loop, and you can also destructuring the assignment (Destructuring Assignment):
The code copy is as follows:
var langs = ['JavaScript', 'Python', 'Haskell'];
var it = Iterators(langs);
for (let [i, lang] in it)
print(i + ': ' + lang); //Output "0: JavaScript" etc.
Declare a custom iterator
Some objects representing a collection of elements should be iterated in a specified way.
1. Iterate over an object representing a range (Range) should return the number contained in this range one by one.
2. A tree's leaf node can be accessed using depth-first or breadth-first
3. Iterating over an object representing the database query results should return row by row, even if the entire result set has not been loaded into a single array.
4. Iterators acting on an infinite mathematical sequence (like Fibonacci sequence) should return results one after another without creating an infinite length data structure.
JavaScript allows you to write code that customizes iterative logic and apply it to an object
We create a simple Range object with two values:
The code copy is as follows:
function Range(low, high){
this.low = low;
this.high = high;
}
Now we create a custom iterator that returns a sequence of all integers in the range. The iterator interface requires us to provide a next() method to return the next element in the sequence or throw a StopIteration exception.
The code copy is as follows:
function RangeIterator(range){
this.range = range;
this.current = this.range.low;
}
RangeIterator.prototype.next = function(){
if (this.current > this.range.high)
throw StopIteration;
else
return this.current++;
};
Our RangeIterator is instantiated by a range instance while maintaining a current property to track the location of the current sequence.
Finally, in order for RangeIterator to be combined with Range, we need to add a special __iterator__ method to Range. When we try to iterate over a Range, it will be called and should return an instance of RangeIterator that implements iterative logic.
The code copy is as follows:
Range.prototype.__iterator__ = function(){
return new RangeIterator(this);
};
After completing our custom iterator, we can iterate over a scope instance:
The code copy is as follows:
var range = new Range(3, 5);
for (var i in range)
print(i); //Output 3, then 4, then 5
Generator: A better way to build iterators
Although custom iterators are a useful tool, you need to carefully plan them when creating them because they need to be explicitly maintained.
The generator provides powerful functions: it allows you to define a function that contains your own iterative algorithm, and it can automatically maintain its state.
A generator is a special function that can be used as an iterator factory. If a function contains one or more yield expressions, it is called a generator (Translator's note: Node.js also needs to be represented by * before the function name).
Note: The yield keyword can only be used for code blocks in HTML that are included in <script type="application/javascript;version=1.7"> (or later). XUL (XML User Interface Language) script tags do not require specifying this special code block to access these features.
When a generator function is called, the function body will not be executed immediately, it will return a generator-iterator object. Each time the next() method of generator-iterator is called, the function body will execute to the next yield expression and then return its result. When the function ends or encounters a return statement, a StopIteration exception will be thrown.
Use an example to better illustrate:
The code copy is as follows:
function simpleGenerator(){
yield "first";
yield "second";
yield "third";
for (var i = 0; i < 3; i++)
yield i;
}
var g = simpleGenerator();
print(g.next()); //Output "first"
print(g.next()); //Output "second"
print(g.next()); //Output "third"
print(g.next()); //Output 0
print(g.next()); //Output 1
print(g.next()); //Output 2
print(g.next()); // Throw a StopIteration exception
Generator functions can be used directly by a class as __iterator__ method, and can effectively reduce the amount of code where custom iterators are needed. Let's rewrite the Range using the generator:
The code copy is as follows:
function Range(low, high){
this.low = low;
this.high = high;
}
Range.prototype.__iterator__ = function(){
for (var i = this.low; i <= this.high; i++)
yield i;
};
var range = new Range(3, 5);
for (var i in range)
print(i); //Output 3, then 4, then 5
Not all generators will terminate, you can create a generator that represents an infinite sequence. The following generator implements a Fibonacci sequence, in which each element is the sum of the first two:
The code copy is as follows:
function fibonacci(){
var fn1 = 1;
var fn2 = 1;
while (1) {
var current = fn2;
fn2 = fn1;
fn1 = fn1 + current;
yield current;
}
}
var sequence = fibonacci();
print(sequence.next()); // 1
print(sequence.next()); // 1
print(sequence.next()); // 2
print(sequence.next()); // 3
print(sequence.next()); // 5
print(sequence.next()); // 8
print(sequence.next()); // 13
Generator functions can take parameters and will use these parameters when the function is called for the first time. The generator can be terminated (causing it to throw a StopIteration exception) by using the return statement. The following fibonacci() variant takes an optional limit parameter that terminates the function when the condition is triggered.
The code copy is as follows:
function fibonacci(limit){
var fn1 = 1;
var fn2 = 1;
while(1){
var current = fn2;
fn2 = fn1;
fn1 = fn1 + current;
if (limit && current > limit)
return;
yield current;
}
}
Generator Advanced Features
The generator can calculate the yield return value based on the requirements, which makes it represent the previously expensive sequence calculation requirements, even the infinite sequence shown above.
In addition to the next() method, the generator-iterator object also has a send() method, which can modify the internal state of the generator. The value passed to send() will be treated as the result of the last yield expression and the generator will be paused. Before you pass a specified value using the send() method, you must call next() at least once to start the generator.
The following Fibonacci generator uses the send() method to restart the sequence:
The code copy is as follows:
function fibonacci(){
var fn1 = 1;
var fn2 = 1;
while (1) {
var current = fn2;
fn2 = fn1;
fn1 = fn1 + current;
var reset = yield current;
if (reset) {
fn1 = 1;
fn2 = 1;
}
}
}
var sequence = fibonacci();
print(sequence.next()); //1
print(sequence.next()); //1
print(sequence.next()); //2
print(sequence.next()); //3
print(sequence.next()); //5
print(sequence.next()); //8
print(sequence.next()); //13
print(sequence.send(true)); //1
print(sequence.next()); //1
print(sequence.next()); //2
print(sequence.next()); //3
Note: Interestingly, calling send(undefined) is exactly the same as calling next(). However, when the send() method is called to start a new generator, a TypeError exception will be thrown except undefined.
You can call the throw method and pass an outlier that it should throw to force the generator to throw an exception. This exception will be thrown from the current context and paused the generator, similar to the current yield execution, but replaced with a throw value statement.
If yield is not encountered during the process of throwing the exception, the exception will be passed until the throw() method is called, and subsequently calling next() will cause the StopIteration exception to be thrown.
The generator has a close() method to force the generator to end. Ending a generator will have the following effects:
1. All valid finally sentences in the generator will be executed
2. If the finally word throws any exception except StopIteration, the exception will be passed to the caller of the close() method.
3. The generator will terminate
Generator expressions
One obvious disadvantage of array derivation is that they cause the entire array to be constructed in memory. The overhead of inputting to the derivation is insignificant when its overhead is a small array itself - however, problems can arise when the input array is large or when creating a new expensive (or infinite) array generator.
The generator allows lazy computing to compute elements as needed when needed. Generator expressions are syntactically almost the same as array derivation - it uses parentheses instead of square brackets (and uses for...in instead of for each...in) - but it creates a generator instead of an array so that the calculation can be delayed. You can think of it as a brief syntax for creating a generator.
Suppose we have an iterator it to iterate over a huge sequence of integers. We need to create a new iterator to iterate over even numbers. An array derivation will create an entire array containing all even numbers in memory:
The code copy is as follows:
var doubles = [i * 2 for (i in it)];
The generator expression will create a new iterator and calculate the even value as needed when needed:
The code copy is as follows:
var it2 = (i * 2 for (i in it));
print(it2.next()); // the first even number in it
print(it2.next()); //The second even number in it
When a generator is used as a parameter of a function, parentheses are used as a function call, meaning that the outermost parentheses can be omitted:
The code copy is as follows:
var result = doSomething(i * 2 for (i in it));
End.