Function-Based Iterators and Generators

Support for iterators and generators as language constructs appeared in javascript only in version 1.7, and one can only dream about using these wonderful things in browsers for a long time. However, it is already possible to use iterators and generators as design patterns in javascript, and moreover, it is quite easy to do it, and sometimes it's nice :)

In my topic, I will often refer to "real iterators", by which I understand the very iterators from javascript 1.7, which in the topic Iterators & Generators perfectly highlighted azproduction.
I highly recommend to get acquainted with his topic, also because for comparison I will use the code of his “real” examples.

So let's go!

Simple example

There is a certain set of objects, let's call them units. You need to give all units the color from the set [red, green, blue] in a cyclical order. That is, the first unit is red, the second is green, the third is blue, the fourth is red again and so on.
')
Such a problem is solved with the help of an auxiliary object, which I usually call Revolver.

var colors = new Revolver(['red', 'green', 'blue']); for (var i = 0; i < units.length; i += 1) { units[i].color = colors.next(); } 

Revolver looks like this:

 function Revolver(items) { this.items = items; this.max = items.length - 1; this.i = -1; } Revolver.prototype.next = function () { this.i = this.i < this.max ? this.i + 1 : 0; return this.items[this.i]; }; 

I don't like this code. You ask why? The answer is: too many gestures. See for yourself, just to paint the units, you had to:

1. declare a helper class
2. define the next () method in this class,
3. create an instance of the class with the desired set of values
4. call the instance's next () method to get the next value from the set.

Is it possible to simplify Revolver so that the code becomes smaller, and the meaning - more?
Can! Use functions, Luke!

 function revolver(items) { var max = items.length - 1, i = -1; return function () { i = i < max ? i + 1 : 0; return items[i]; }; } var next_color = revolver(['red', 'green', 'blue']); for (var i = 0; i < units.length; i += 1) { units[i].color = next_color(); } 

Now there is no class with a method, instead there is a function that returns a function.
The concentration of meaning is maximum, because in reality we need not a set of colors as an object, but a method of obtaining the next color from the set .

The method of obtaining an element of a collection in the absence of a collection as such is what is called an iterator.

Theory

An iterator is an object that allows a programmer to iterate over all elements of a collection without taking into account the peculiarities of its implementation (wikipedia).

In the example above, the collection is an infinite repeating color set of r, g, b, r, g, b, ..., and the implementation features of the collection are really hidden.

Iterators are produced by generators. The generator looks like a function that remembers where the previous return was, and on the next call resumes operation from the interrupted place. A generator is a factory of iterators of a certain type; after a generator is called, each iterator created by it lives its own life.

In the example, the revolver function is a generator of infinite iterator sequences from a transmitted set of elements.

Thus, functional iterators and generators can be defined as:

1. Iterator - a function that returns items of a collection during successive calls;
2. The generator is a function that returns an iterator function.

A traditional example of the use of generators is the generation of infinite sequences, such as the Fibonacci sequence. Let's see how it can be implemented as a functional generator.

 function fibonacci() { var fn1 = 1, fn2 = 1; return function () { var current = fn1; fn1 = fn2; fn2 = fn2 + current; return current; }; } var sequence = fibonacci(); for (var i = 0; i < 5; i += 1) { console.log(sequence()); // 1, 1, 2, 3, 5 } 

Works! Compare with the code of this generator:

 function fibonacci(){ var fn1 = 1, fn2 = 1; while (1) { var current = fn1; fn1 = fn2; fn2 = fn2 + current; yield current; } } 

It seems true?

Practice

One of the purposes of iterators is to organize a looping through of the collection, the interface to which they represent.

These iterators are perfectly integrated into the for i in loop operator. To mark the end of a collection, the iterator throws a special exception, which the for statement understands as a loop exit signal.

Obviously, the way the functional iterators work should be different.

The first thing you need to decide is the designation of the end of the collection. For this, it is convenient to use the following property of javascript functions: if the return statement is not encountered until the end of the function body, the result of the function execution is undefined. This feature allows you to make the iterator code more understandable and readable: as long as there are elements of the collection, we return them with the help return, when the elements have run out, we don’t return anything.

The second is a construct with which a functional iterator can be iterated. The construction is needed not only for the iterator, but also for the generator. Everything is also quite simple:

 //  — while var item; while (item = iterator()) { //  item } //  — for for (var item, iter = generator(); item = iter();) { //  item } 

Example of the organization of the cycle: a generator of powers of two, not exceeding the number N.

 function powers_of_two(N) { var value = 1; return function () { var result = value; value *= 2; if (result < N) { return result; } }; } for (var p, iter = powers_of_two(42); p = iter();) { console.log(p); // 1, 2, 4, 8, 16, 32 } 

A fly in the ointment

Real generators have an important property, which is to resume execution of the iterator body from the point of calling the last yield statement. This functionality allows the linear code to describe a sequence of elements that are usually generated using loops or recursion, and thus simplify the code.

A good example is the tree traversal generator from the Iterators & Generators topic:

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

It looks clear and logical - we return the elements of the left branch, then the root, then the elements of the right branch. The class.

Functional generators cannot continue executing the code after the return statement; each iterator call leads to the execution of the function from the beginning. Therefore, the state has to be saved in variables closed on an iterator function.

Let's try to create a functional generator of recursive tree traversal.
Attempt 1, duplication of the logic of the present generator:

 function inorder(t) { var root = false, left, right; if (t) { left = inorder1(t.left); right = inorder1(t.right); return function () { var item; if (item = left()) { return item; } if (!root) { root = true; return t.label; } if (item = right()) { return item; } }; } else { return function () {}; } } 

It turned out so-so, but two things are especially sad.

1. The presence of three return statements in the body of the iterator. In the case of the yield statement, everything looks logical, since execution continues from the next line. However, if return is used as a yield, the logic is broken and it becomes more difficult to understand what is going on.

2. An empty tree at the input of the generator is processed by a separate empty iterator return function () {} , which further confuses the code.

The source of problems in this case is the copying of the logic of the present generator, which is able to maintain its state. To make the function generator code clear, you need to save the state more clearly.

We will think over iteration on a tree.
Obviously, it is necessary to operate with iterators on the nodes of the left and right branches of the tree.
When the left branch iterator is used up, you need to use the root, then use the right branch iterator.
If it were possible to represent the root in the form of an iterator, we would have three iterators, each of which needs to be consistently used to the end, returning the result, after which the tree will be completed completely.

Let's try to translate in code:

 function inorder(t) { var roots = [t], //     iters = []; if (t) { iters.push(inorder(t.left)); iters.push(function () {return roots[0] && roots.shift().label}); //   iters.push(inorder(t.right)); } return function () { var leaf; while (iters.length) { leaf = iters[0](); if (leaf) { return leaf; } iters.shift(); } }; } 

It turned out almost well - the return statement in the iterator is one, and the iterator code is very simple.

Thus, functional generators with complex logic are quite realizable, but their creation requires more careful deliberation in comparison with real generators.

Iterator Management

Especially meticulous guys might object to me at the beginning of the topic, for example, like this: “Wait a minute, you say that the iterator is a function. Great, but what will you do with this function if you need to reset the state of the iterator? ”

I answer: I will add a method to this function :) Functions in javascript are objects. Of course, functions may have methods.

The good old Fibonacci sequence, now with the reset method:

 function fibonacci_restartable() { var fn1 = 1, fn2 = 1, iterator; iterator = function () { var current = fn1; fn1 = fn2; fn2 = fn2 + current; return current; }; iterator.restart = function () { fn1 = fn2 = 1; }; return iterator; } var sequence = fibonacci_restartable(); for (var i = 0; i < 5; i += 1) { console.log(sequence()); // 1, 1, 2, 3, 5 } sequence.restart(); for (var i = 0; i < 5; i += 1) { console.log(sequence()); // 1, 1, 2, 3, 5 } 

If you use terminology, the restart method is preferred , which actually means the presence of a closure on the iterator's internal variables.
Similarly, you can add an iterator with any necessary methods that affect its internal state.

findings

Iterators and generators in the form of design patterns get along quite well in javascript due to the flexibility of its functions. Of course, functional iterators are inferior in performance to real iterators, but in places where performance is not important, the use of functional iterators can streamline and simplify the code.

Thank you for attention!