Iterators & Generators

Processing elements of a collection / array is a common and frequent operation. There are several ways to bypass the collection in JavaScript, starting with a simple for(;;) and for a in b

 var divs = document.querySelectorAll('div'); for (var i = 0, c = divs.length; i < c; i++) { console.log(divs[i].innerHTML); } 

 var obj = {a: 1, b: 2, c: 3}; for (var i in obj) { console.log(i, obj[i]); } 

The Array object has methods to bypass all map(), filter() elements.

 var numbers = [1, 2, 3, 4, 5]; var doubled = numbers.map(function (item) { return item * 2; }); console.log(doubled); 

Firefox has an array filler (Array comprehensions)

 var numbers = [1, 2, 3, 4]; var doubled = [i * 2 for each (i in numbers)]; console.log(doubled); // [2, 4, 6, 8] 

Iterators and Generators appeared in JavaScript 1.7 (according to Mozilla) they still exist in Firefox 2+ (the article will mention the way how they can be “emulated” in almost all browsers with a crutch) Iterators and Generators introduce a mechanism that allows you to control for in and encapsulate the process of getting the next item in the list of objects.

Often, to traverse and process the elements of an array, we write large constructions, often copy-pasting their parts. The task of Generators and Iterators is to improve this process by adding syntactic sugar.

Iterators

Everyone knows that in JavaScript you can bypass almost any object:
Array

 var object = [1,2,3]; for (var i in object) { console.log(i, object[i]); } 

An object

 var object = {a:1, b:2, c:3}; for (var i in object) { console.log(i, object[i]); } 

Line

 var object = 'abc'; for (var i in object) { console.log(i, object[i]); } 

Some list

 var object = document.querySelectorAll('div'); for (var i in object) { if (object.hasOwnProperty(i)) { console.log(i, object[i]); } } 

We traverse all objects sequentially and cannot control the sequence. Iterators have a similar interface, but provide the ability to manage items:
')
An iterator is an object that knows how to access the elements of a collection one at a time, keeping its current position (cursor) in this sequence. In JavaScript, an iterator is an object that has a next() method that returns the next object in the sequence. This method can cause a StopIteration exception when the sequence has ended.

The iterator can be used in different ways: directly through a call to the next() method or using for...in or for each (FF) constructs.

There are several ways to create an iterator:

Call Iterator function

 var lang = { name: 'JavaScript', birthYear: 1995 }; var it = Iterator(lang); // <<< 

After creating an iterator, the it object can be iterated using next()

 var pair = it.next(); //  ["name", "JavaScript"] pair = it.next(); //  ["birthYear", 1995] pair = it.next(); //    StopIteration 

For traversal, you can use for...in or for each . The traversal will be stopped as soon as the exception StopIteration is thrown:

 var it = Iterator(lang); for (var pair in it) { console.log(pair); // 2  [key, value] } 

One of the advantages of Iterator() is that it bypasses only its own properties (remember the example of traversing querySelectorAll ) while traversing you do not need to check object.hasOwnProperty .

Iterator() can also be used for an array:

 var langs = ['JavaScript', 'Python', 'C++']; var it = Iterator(langs); for (var pair in it) { console.log(pair); // [index, language] } 

If the Iterator function Iterator second argument, then only the indices will be iterated:

 var langs = ['JavaScript', 'Python', 'C++']; var it = Iterator(langs, true); for (var pair in it) { console.log(pair); // 0, 1, 2 } 

For the index and value, you can select your own variables using let and destructive assignment (FF only):

 var langs = ['JavaScript', 'Python', 'C++']; var it = Iterator(langs); for (let [i, lang] in it) { //  FF console.log(i + ': ' + lang); //  "0: JavaScript" . } 

This way of creating iterators is not very useful and is similar to the usual for in without Iterator .

Creating your own iterators

Some objects are a collection of items that need to be iterated in a special way. For example:
- Iteration of the Range object should return the numbers included in the set.
- Tree leaves can be bypassed using a wide search or a depth search.
- The results of the query to the database are returned as an object that can be iterated and return the data set in one record.
- An iterator of an infinite mathematical sequence (for example, a Fibonacci sequence) must return results one by one without creating an array of infinite length.

Let's create a simple Range object that stores a range.

 function Range(low, high){ this.low = low; this.high = high; } 

Now create your iterator, which returns a sequence of this range. The iterator interface requires us to create a next() method that will return an element of the sequence and throw a StopIteration exception at the end.

 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++; }; 

 var ri = new RangeIterator(new Range(1, 10)); ri.next(); // ... ri.next(); // StopIteration 

Somehow not very comfortable. To get rid of the RangeIterator constructor, RangeIterator will use the __iterator__ method __iterator__ the Range object. This method will be called when trying to iterate over the elements of a Range object. This method should return a RangeIterator that includes the iterator logic.

 Range.prototype.__iterator__ = function(){ return new RangeIterator(this); }; var range = new Range(3, 5); for (var i in range) { console.log(i); // 3, 4, 5 } 

Conveniently enough, but a lot of excess.

Generators

Arbitrary iterators are handy, but creating them requires careful programming and memorizing the internal state. Generators are a more common alternative. They allow you to define an alternative algorithm using one function that remembers its state (a kind of finite automaton).

A generator is a special type of function that works as a factory for creating iterators. Any function containing at least one yield becomes a generator.

Note: In the original, generators are only available in Firefox 2+ with an overridden version of JavaScript <script type="application/javascript;version=1.7">

When a generator function is called its body is not executed. It works as a constructor that creates and returns an Iterator-Generator. Each call to the Iterator-Generator method next() will perform the function body until a yield is returned that returns a result. If the function ends with return or the function body ends, the StopIteration exception is StopIteration and the iterator stops its operation.

We describe in the example:

 function simpleGenerator(){ yield "first"; yield "second"; yield "third"; for (var i = 0; i < 3; i++) { yield i; } } var g = simpleGenerator(); console.log(g.next()); // "first" console.log(g.next()); // "second" console.log(g.next()); // "third" console.log(g.next()); // 0 console.log(g.next()); // 1 console.log(g.next()); // 2 console.log(g.next()); // StopIteration 

The Generator function can be used as the __iterator__ method of an __iterator__ object. This will significantly reduce the amount of code. Let's rewrite the example from Range using generators:

 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) { console.log(i); // 3, 4, 5 } 

It turned out 3 times shorter

With the help of generators you can create endless sequences. Let us examine an example of Fibonacci numbers:

 function fibonacci(){ var fn1 = 1; var fn2 = 1; while (1){ var current = fn2; fn2 = fn1; fn1 = fn1 + current; yield current; } } var sequence = fibonacci(); console.log(sequence.next()); // 1 console.log(sequence.next()); // 1 console.log(sequence.next()); // 2 console.log(sequence.next()); // 3 console.log(sequence.next()); // 5 console.log(sequence.next()); // 8 // ... 

Generator functions can pass arguments. You can interrupt generators using StopIteration or return . Rewrite the Fibonacci example using the limit argument.

 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; } } var sequence = fibonacci(7); console.log(sequence.next()); // 1 console.log(sequence.next()); // 1 console.log(sequence.next()); // 2 console.log(sequence.next()); // 3 console.log(sequence.next()); // 5 console.log(sequence.next()); // StopIteration 

Advanced Generators

Generators calculate their next value on request. This allows you to create sequences that are difficult to calculate or they are infinite, as in the example above.

In addition to the next() method, the Iterator-Generator has a send() method that allows you to change the internal state of the generator. The value passed to send() will be perceived as the result of the last yield that stopped the generator. You must start the generator with next() before calling send() .

Here is a rewritten Fibonacci generator using send() to restart the sequence:

 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.send(true)); // 1 print(sequence.next()); // 1 print(sequence.next()); // 2 print(sequence.next()); // 3 

You can force the generator to throw an exception by calling the throw() method. This method takes one argument, which will throw the generator ( throw value; ). This exception will be thrown from the current stopped generator context (in the place where the last yield ).

If the generator was not started (there was no call to the next() method), then throw() will call next() and throw an exception at the yield .

You can close the generator using the close() method:
This method does the following:
- All finally blocks will be executed.
- If the finally block throws an exception other than StopIteration , then the exception will be thrown into the context from which the close() method was called
- The generator is destroyed

Generators Expressions

The “array placeholder” has one significant drawback when it is called; it fills the array and takes up memory. When an array is small, it is invisible, in the case of large arrays, it is very expensive, and in the case of an infinite number of elements, the Array array does not make sense.

Generators perform calculations on demand. Generator expressions are similar to “Array placeholders”, but instead of creating an array, Generator expressions create iterator generators that are executed on demand. You can call them short generators.

Suppose we have an iterator that bypasses a large number of integers. We want to create a new iterator that will iterate over duplicate numbers. Using the "Array Filler" we will create a whole array in memory containing the multiplied values:

 var doubles = [i * 2 for (i in it)]; 

Generators expressions will create a new iterator that will multiply the numbers on demand:

 var it2 = (i * 2 for (i in it)); print(it2.next()); //    print(it2.next()); //    

An expression generator can be passed as an argument to a function. Additional brackets in this case can be omitted:

 var result = doSomething(i * 2 for (i in it)); 

Examples

Doubles of numbers, Finobacci sequence is very cool, but somehow far from life. Let's look at life examples:

1. Traversing the DOM tree

On the page there are several links. For each, you need to get a domain and innerHTML and if innerHTML matches the domain, output the domain to the console.

Links for test:

 <a href="http://ya.ru/"> </a> <a href="http://google.ru/"></a> <a href="http://habrahabr.ru/"></a> <a href="http://twitter.com/">twitter.com</a> 

Our code to Generators:

 var aList = document.querySelectorAll('a'); for (var i = 0, c = aList.length, a, content, domain; i < c; i++) { a = aList[i]; content = a.innerHTML; domain = a.getAttribute('href').replace('http://', '').split('/').shift(); if (content === domain) { console.log(domain); } } 

Everything is natural and understandable. And if we need to use this cycle for other checks? Skopipastim code? Generators helps;) Rewrite:

  //    type="application/javascript;version=1.7" var aDomainContentGenerator = function () { var aList = document.querySelectorAll('a'); for (var i = 0, c = aList.length, a, content, domain; i < c; i++) { a = aList[i]; content = a.innerHTML; domain = a.getAttribute('href').replace('http://', '').split('/').shift(); yield {domain: domain, content: content}; } }; var ancors = aDomainContentGenerator(); //  -      //   for c if,   . ,     var ancorsWithSameContentAndDomain = (item for (item in ancors) if (item.content === item.domain)); for (item in ancorsWithSameContentAndDomain) { console.log(item.domain); } 

The code has turned out a little more, but the code has grown in width (this is an important plus) and now we can use the aDomainContentGenerator() generator for other purposes.

2. Traversing the tree

There is a tree in which lines are scattered. You must display them in ascending order:

 function Tree(left, label, right) { this.left = left; this.label = label; this.right = right; } //      function inorder(t) { if (t) { for (var item in inorder(t.left)) { yield item; } yield t.label; for (var item in inorder(t.right)) { yield item; } } } //    function make(array) { //  : if (array.length == 1) return new Tree(null, array[0], null); return new Tree(make(array[0]), array[1], make(array[2])); } var tree = make([[['a'], 'b', ['c']], 'd', [['e'], 'f', ['g']]]); //  for (var node in inorder(tree)) { console.log(node); // a, b, c, d, ... } 

There was one bulky structure in the code.

 for (var item in inorder(t.right)) { yield item; } 

Which in the future they want to replace with:

 yield for inorder(t.right); 

Generators can be used for

- Beautiful iteration of iterated objects: lists (lines in a file, query result to a database,), recursive traversal of trees (XML, HTML, Binary, and other arbitrary), creation and traversing of Range objects (0..10)
- Bypass access logs. For example, there are several rotated access logs. It is necessary to collect information about the amount of transferred data.
- yield can act as a breakpoint during debug
- Can be used to split a long cycle into several parts (both in time and in the number of processed cycle elements)
- Pseudo-random number generator or sequence
- Basis for Wizards / Wizards (step-by-step interface)
- Can be used to change the behavior of an event (for example, clicking on a button)

Generator Benefits

1. Perform on-demand calculations
2. Do not take up extra memory
3. Encapsulate the process of getting a collection item.
4. Stretch the code
5. Generators can be used as filters, sticking together in the pipeline

Performance

Judging by the Python tests Generators are not inferior to normal cycles. Read more in the presentation " Generator Tricks For Systems Programmers An Introduction " (Slide 22)
According to the Generator vs Common Loop test, the generators are one third slower than the cycle.

When can it be used?

In Firefox 2+ with an override of JavaScript, you can write right now. The rest is getting worse. There is one good project - Google traceur-compiler. This compiler allows you to process future ES6 + code into ES3 code. But this is not a panacea, the code from the “Tree Traversal” example did not work in any browser
TC does not understand for..in cycles of generators:

 for (var node in inorder(tree)) { console.log(node); // a, b, c, d, ... } 

He needs

 for (let node : inorder(tree)) { console.log(node); // a, b, c, d, ... } 

But this view does not understand Firefox. TC requires Function#bind , Object.defineProperty so the compiled version only works in the TC creator’s browser, Google Chrome :). The compiled code of the generator is obtained monstrous with the use of a finite state machine and dances around try catch and other perversions. It turns out this "code":

 function Tree(left, label, right) { this.left = left; this.label = label; this.right = right; } function inorder(t) { var $that = this; return { __traceurIterator__: function() { var $state = 20; var $storedException; var $finallyFallThrough; var $__1; var $__2; var $__3; var $__4; var $result = { moveNext:(function() { while(true) try { switch($state) { case 20: if(t) { $state = 7; break; } else { $state = 15; break; } case 7: $__2 = inorder(t.left).__traceurIterator__(); $state = 8; break; case 8: if($__2.moveNext()) { $state = 2; break; } else { $state = 5; $finallyFallThrough = 4; break; } case 2: $__1 = $__2.current; $state = 3; break; case 3: $result.current = $__1; $state = 8; return true; case 5: { if($__2.close) $__2.close(); } $state = 6; break; case 4: $result.current = t.label; $state = 10; return true; case 10: $__4 = inorder(t.right).__traceurIterator__(); $state = 19; break; case 19: if($__4.moveNext()) { $state = 13; break; } else { $state = 16; $finallyFallThrough = 15; break; } case 13: $__3 = $__4.current; $state = 14; break; case 14: $result.current = $__3; $state = 19; return true; case 16: { if($__4.close) $__4.close(); } $state = 17; break; case 6: $state = $finallyFallThrough; break; case 17: $state = $finallyFallThrough; break; case 15: $state = 22; case 22: return false; case 21: throw $storedException; default: throw "traceur compiler bug: invalid state in state machine" + $state; } } catch($caughtException) { $storedException = $caughtException; switch($state) { case 8: $state = 5; $finallyFallThrough = 21; break; case 2: $state = 5; $finallyFallThrough = 21; break; case 3: $state = 5; $finallyFallThrough = 21; break; case 19: $state = 16; $finallyFallThrough = 21; break; case 13: $state = 16; $finallyFallThrough = 21; break; case 14: $state = 16; $finallyFallThrough = 21; break; default: throw $storedException; } } }).bind($that) }; return $result; } }; } function make(array) { if(array.length == 1) return new Tree(null, array[0], null); return new Tree(make(array[0]), array[1], make(array[2])); } var tree = make([[['a'], 'b',['c']], 'd',[['e'], 'f',['g']]]); { var $__0 = inorder(tree).__traceurIterator__(); try { while($__0.moveNext()) { try { throw undefined; } catch(node) { node = $__0.current; { console.log(node); } } } } finally { if($__0.close) $__0.close(); } } 

Code for half the article - left to show that everything is bad with him ...

Conclusion

In the original Generators can only be used in Firefox, and therefore can not be used (but you can play). Even if you finish Function#bind and Object.defineProperty , in any case, TC turns the code into a brake monster and therefore its use is questionable.

The only place where they can be successfully applied is the future SpiderNode . Iterators and Generators are an incredibly useful thing. On the client, we will use them in 5 years (for all known reasons). On the server, I hope, in the near future.

Read

1. MDC - Array comprehensions
2. ES Harmony Iterators
3. ES Harmony Generators
4. MDC - MDC Iterators and Generators Guide
5. MDC - New in JavaScript 1.7
6. traceur-compiler LanguageFeatures

JavaScript adopted 1-in-1 generators and iterators from Python, but there are few examples in JavaScript. Kinu Palu links to resources Python:
7. PEP 380, " Syntax for delegating to a sub-generator "
8. PEP 255, " Simple generators "
9. Presentation of " Generator Tricks For Systems Programmers An Introduction "

Suggestions, suggestions, criticism are welcome!

UPD Added generator performance test Generator vs Common Loop