Iterators & Generators

Обработка элементов коллекции/массива обычная и частая операция. В JavaScript есть несколько способов обхода коллекции начиная с простого for(;;) и 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]);
}

У объекта Array есть методы обхода всех элементов map(), filter()

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

В Firefox есть "заполнитель массива" (Array comprehensions)

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

Итераторы и Генераторы появились в JavaScript 1.7 (по версии Mozilla) они есть пока в Firefox 2+ (в статье будет упомянут способ как их можно «эмулировать» почти во всех браузерах с костылем) Итераторы и Генераторы вносят механизм, позволяющий управлять поведением for in и инкапсулировать процесс получения следующего элемента в списке объектов.

Часто для обхода и обработки элементов массива мы пишем большие конструкции, часто копипастим их части. Задача Генераторов и Итераторов усовершенствовать этот процесс, добавив синтаксический сахар.

Итераторы

Все знают, что в JavaScript можно и так обходить практически любой объект:
Массив

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

Объект

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

Строка

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

Какой-то список

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

Мы обходим все объекты последовательно и не можем управлять последовательностью. Итераторы имеют похожий интерфейс, но предоставляют возможность управлять элементами:

Итератор — это объект, который знает как получить доступ к элементам коллекции по одному за раз, сохраняя свою ткущую позицию (курсор) в этой последовательности. В JavaScript итератор — это объект, который имеет метод next(), который возвращает следующий объект в последовательности. Этот метод может вызывать исключение StopIteration, когда последовательность закончилась.

Итератор может использоваться разными способами: напрямую через вызов метода next() или используя конструкции for...in или for each(только FF).

Существует несколько способов создания итератора:

Вызов функции Iterator

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

После создание итератора объект it можно итерировать используя next()

var pair = it.next(); // Врзвращает ["name", "JavaScript"]
pair = it.next(); // Врзвращает ["birthYear", 1995]
pair = it.next(); // Будет выброшено исклюение StopIteration

Для обхода можно использовать for...in или for each. Обход будет остановлен как только будет выброшено исключение StopIteration:

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

Один из плюсов Iterator() в том, что он обходит только собственные свойства (вспомните пример обхода querySelectorAll) при обходе вам не нужно проверять object.hasOwnProperty.

Iterator() может использоваться и для массива:

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

Если функции Iterator передать второй аргумент, то итерироваться будут только индексы:

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

Для индекса и значения можно выделить собственные переменные, используя let и деструктивное присваивание(Только FF):

var langs = ['JavaScript', 'Python', 'C++'];
var it = Iterator(langs);
for (let [i, lang] in it) { // Только FF
    console.log(i + ': ' + lang); // напечатает "0: JavaScript" итд.
}

Этот способ создания итераторов не очень полезный и похож на обычный for in без Iterator.

Создание своих итераторов

Некоторые объекты представляют из себя коллекцию элементов, которые должны итерироваться особым образом. Например:
— Итерация объекта Range должна возвращать числа входящие в множество.
— Листья деревьев можно обходить используя поиск в ширину или поиск в глубину
— Результаты запроса к БД возвращаются в виде объекта, который может итерироваться и возвращать набор данных в одной записи.
— Итератор бесконечной математической последовательности (например, последовательность Фибоначчи) должен возвращать результаты один за другим без создания массива бесконечной длины.

Давайте создадим простой объект Range, хранящий диапазон.

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

Теперь создадим свой итератор, который возвращает последовательность из этого диапазона. Интерфейс итератора требует, чтобы мы создали метод next(), который возвратит элемент последовательности и в конце выбросит исключение StopIteration.

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

Как-то не очень удобно. Чтобы избавиться от конструктора RangeIterator будем использовать метод __iterator__ у объекта Range. Этот метод будет вызван при попытке итерировать элементы объекта Range этот метод должен возвратить RangeIterator, включающий логику итератора.

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
}

Достаточно удобно, но много лишнего.

Генераторы

Произвольные итераторы удобная штука, но их создание требует аккуратного программирования и запоминания внутреннего состояния. Генераторы — это более общая альтернатива. Они позволяют определить альтернативный алгоритм, используя одну функцию, которая запоминает свое состояние (подобие конечного автомата).

Генератор это специальный тип функций, которая работает как фабрика по созданию итераторов. Любая функция, содержащая хотя бы один yield становится генератором.

Внимание: В оригинале генераторы доступны только в Firefox 2+ с переопределенной версией JavaScript <script type="application/javascript;version=1.7">

Когда функция генератора вызывается его тело не выполняется. Она работает как конструктор, который создает и возвращает Итератор-Генератор. Каждый вызов метода Итератор-Генератора next() будет выполнять тело функции до тех пор пока не попадется yield, которая возвратит результат. Если функция завершится с return или тело функции закончится будет выброшено исключение StopIteration и итератор прекратит свою работу.

Опишем в примере:

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

Функция-Генератор может быть использована в качестве метода __iterator__ у объекта-итератора. Это позволит значительно уменьшить объем кода. Перепишем пример с Range используя генераторы:

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
}

Получилось раза в 3 короче

С помощью генераторов можно создавать бесконечны последовательности. Разберем пример чисел Фибоначчи:

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
// ...

Функциям-генераторам можно передавать аргументы. Можно прерывать генераторы, используя StopIteration или return. Перепишем пример с числами Фибоначчи, используя аргумент limit.

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

Продвинутые Генераторы

Генераторы вычисляют свое следующее значение по запросу. Это позволяет создавать последовательности, которые сложно вычисляются или они бесконечны, как в примере выше.

В дополнении к методу next(), Генератор-Итератор имеет метод send() он позволяет изменить внутреннее состояние генератора. Значение переданное в send() будет восприниматься как результат последнего yield, остановившего генератор. Вы обязаны запустить генератор с помощью next() перед тем как вызывать send().

Вот переписанный Фибоначчи генератор, использующий send() для рестарта последовательности:

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

Вы можете заставить генератор выбросить исключения, вызвав метод throw(). Этот метод принимает один аргумент, который и выбросит генератор (throw value;). Это исключение будет выброшено из текущего остановленного контекста генератора (в том месте где был последний yield).

Если генератор не был запущен (не было вызова метода next()), то throw() вызовет next() и в месте yield выбросит исключение.

Вы можете закрыть генератор, используя метод close():
Этот метод делает следующее:
— Все finally блоки будут выполнены
— Если finally блок выбрасывает исключение отличное от StopIteration, то исключение будет проброшено в контекст из которого был вызван метод close()
— Генератор уничтожается

Генераторы-Выражения

«Заполнитель массива» имеет один значительный недостаток при вызове он заполняет массив и занимает память. Когда массив небольшой то это незаметно, в случае с большими массивами это очень дорого, а в случае с бесконечным количеством элементов «Заполнитель массива» не имеет смысла.

Генераторы выполняют вычисления по требованию. Генераторы-выражения схожи с «Заполнителями массива», но вместо создания массива Генераторы-выражения создают итератор-генераторы, которые выполняются по требованию. Вы можете назвать их короткими генераторами.

Предположим, что у нас есть итератор, который обходит большое количество целых чисел. Мы хотим создать новый итератор, который будет итерировать дубли чисел. Используя «Заполнитель массива» мы создадим целый массив в памяти, содержащий умноженные значения:

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

Генераторы-выражения создадут новый итератор, который будет умножать числа по требованию:

var it2 = (i * 2 for (i in it));
print(it2.next()); // Первое удвоенное значение
print(it2.next()); // Второе удвоенное значение

Генератор-выражение можно передавать в качестве аргумента функции. Дополнительные скобки в этом случае можно упустить:

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

Примеры

Дубли чисел, последовательность Финобаччи это очень круто, но как-то далеко от жизни. Посмотрим примеры из жизни:

1. Обход DOM дерева

На странице есть несколько ссылок. Для каждой необходимо получить домен и innerHTML и если innerHTML совпадает с доменом вывести домен в консоль.

Ссылки для теста:

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

Наш код до Генераторов:

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

Все естественно и понятно. А если этот цикл нам нужно будет использовать ещё для других проверок? Скопипаcтим код? Генераторы helps ;) Перепишем:

 // Не забываем про 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);
}

Кода получилось немного больше, но код вырос в ширину(это важный плюс) и теперь мы можем использовать генератор aDomainContentGenerator() и для других целей.

2. Обход дерева

Есть дерево в котором разбросаны строки. Необходимо вывести их в порядке возрастания:

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, ...
}

В коде была одна громоздкая структура

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

Которую в будущем хотят заменить на:

yield for inorder(t.right);

Генераторы можно применить для

— Красивого обхода итерируемых объектов: списков (строки в файле, результат запроса к БД, ), рекурсивного обхода деревьев (XML, HTML, Binary, и других произвольных), создание и обход Range-объектов (0..10)
— Обход access логов. Например есть несколько ротированных access-log'ов необходимо собрать информацию об объеме переданных данных
— yield может выполнять роль точки остановки при дебаге
— Можно использовать для разбиения длинного цикла на несколько частей (как по времени так и по количеству обработанных элементов цикла)
— Генератор псевдослучайных чисел или последовательностей
— Основа для Визардов/Мастеров (пошаговый интерфейс)
— Могут использоваться для изменения поведения события (например клика на кнопку)

Преимущества генераторов

1. Выполняют вычисления по требованию
2. Не занимают лишнюю память
3. Инкапсулируют процесс получения элемента коллекции
4. Растягивают код
5. Генераторы можно применять как фильры, склеивая в pipeline

Производительность

Судя по питоновским тестам Генераторы не уступают обычным циклам. Подробнее в презентации "Generator Tricks For Systems Programmers An Introduction" (Слайд 22)
По тесту Generator vs Common Loop генераторы на треть медленнее цикла.

Когда это можно будет использовать?

В Firefox 2+ с оверрайдом версии JavaScript можно писать прям сейчас. С остальными все хуже. Существует один хороший проект — Google traceur-compiler. Этот компилятор позволяет обработать код будущих версий ES6+ в код ES3. Но это не панацея, код из примера «Обход дерева» не заработал ни в одном браузере
TC не понимает циклы for..in у генераторов:

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

Ему нужно

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

Но такой вид не понимает Firefox. TC требует Function#bind, Object.defineProperty поэтому скомпилированная версия работает только в браузере создателя TC — Google Chrome :). Скомпилированный код генератора получается монстрообразным с применением конечного автомата и плясок вокруг try catch и прочих извратов. Получается такой «код»:

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

Код на половину статьи — оставил, чтобы показать, что с ним все плохо...

Заключение

В оригинале Генераторы можно использовать только в Firefox, а значит использовать нельзя (но поиграть можно). Даже если допилить Function#bind и Object.defineProperty, то в любом случае TC превращает код в тормозного монстра и поэтому его применение сомнительное.

Единственный место где их можно удачно применить — будущий SpiderNode. Итераторы и Генераторы невероятно полезная штука. На клиенте мы будем ими пользоваться лет через 5 (по всем известным причинам). На сервере, надеюсь, в ближайшее время.

Почитать

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 перенял генераторы и итераторы 1-в-1 из Python, но примеров на JavaScript пока мало. Кину палу ссылок на ресурсы Python:
7. PEP 380, "Syntax for delegating to a sub-generator"
8. PEP 255, "Simple generators"
9. Презентация "Generator Tricks For Systems Programmers An Introduction"

Предложения, пожелания, критика приветствуются!

UPD Добавил тест производительности генераторов Generator vs Common Loop