Pull to refresh

Итераторы и генераторы на основе функций

Reading time 6 min
Views 4.9K
Поддержка итераторов и генераторов в качестве языковых конструкций появилась в javascript только в версии 1.7, и об использовании этих чудесных вещей в браузерах еще долго можно будет только мечтать. Однако использовать итераторы и генераторы в виде паттернов проектирования в javascript можно уже сейчас, и более того, делать это достаточно легко, а иногда даже приятно :)

В моем топике я часто буду ссылаться на «настоящие итераторы», под которыми понимаю те самые итераторы из javascript 1.7, которые в топике Iterators & Generators отлично осветил azproduction.
Я настоятельно рекомендую с ознакомиться с его топиком, еще и потому, что для сравнения я буду использовать код его «настоящих» примеров.

Итак, поехали!

Простой пример


Имеется некий набор объектов, назовем их юнитами. Нужно задать всем юнитам цвет из набора [красный, зеленый, синий] в циклическом порядке. То есть первый юнит — красный, второй — зеленый, третий — синий, четвертый — снова красный и так далее.

Такая задача решается с помощью вспомогательного объекта, который я обычно называю Revolver.

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

Revolver выглядит следующим образом:

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

Этот код мне не нравится. Вы спрашиваете, почему? Отвечаю: слишком много телодвижений. Смотрите сами, чтобы всего лишь раскрасить юниты, пришлось:
  1. объявить вспомогательный класс,
  2. определить метод next() в этом классе,
  3. создать экземпляр класса с нужным набором значений,
  4. вызывать метод next() экземпляра для получения следующего значения из набора.

Можно ли упростить Revolver так, чтобы кода стало поменьше, а смысла — побольше?
Можно! 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();
}

Теперь нет никакого класса с методом, вместо него есть функция, возвращающая функцию.
Концентрация смысла — максимальная, ведь на самом деле нам нужен не набор цветов в виде объекта, а метод получения следующего цвета из набора.

Метод получения элемента коллекции при отсутствии коллекции как таковой и есть то, что назвается итератором.

Теория


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

В приведенном примере коллекция — бесконечный повторяющийся набор цветов r, g, b, r, g, b, ..., и особенности реализации коллекции действительно скрыты.

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

В примере функция revolver — генератор бесконечных итераторов последовательностей из переданного набора элементов.

Таким образом, функциональные итераторы и генераторы можно определить так:
  1. Итератор — функция, при последовательных вызовах возвращающая элементы коллекции;
  2. Генератор — функция, возвращающая функцию-итератор.

Традиционный пример применения генераторов — генерация бесконечных последовательностей, таких как последовательность Фибоначчи. Посмотрим как её можно реализовать в виде функционального генератора.

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
}

Работает! Сравните с кодом настоящего генератора:

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

Похоже, правда?

Практика


Одно из назначений итераторов — организация циклического перебора коллекции, интерфейс к которой они представляют.

Настоящие итераторы отлично встраиваются в оператор цикла for i in. Для обозначения конца коллекции итератор выбрасывает специальное исключение, которое оператор for понимает как сигнал выхода из цикла.

Очевидно, что способ работы функциональных итераторов должен отличаться.

Первое, с чем нужно определиться, — это обозначение окончания коллекции. Для этого удобно использовать следующее свойство функций javascript: если до конца тела функции не встретился оператор return, то результатом выполнения функции будет undefined. Эта особенность позволяет cделать код итератора более понятным и читаемым: пока есть элементы коллекции, возвращаем их с помощью return, когда элементы закончились — не возвращаем ничего.

Второе — это конструкция, с помощью которой функциональный итератор можно перебирать. Конструкция нужна не только для итератора, но и для генератора. Тут всё тоже достаточно просто:

// Итераторам — while
var item;
while (item = iterator()) {
    // обрабатываем item
}

// Генераторам — for
for (var item, iter = generator(); item = iter();) {
    // обрабатываем item
}

Пример организации цикла: генератор степеней двойки, не превышающих числа 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
}


Ложка дегтя, куда же без нее

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

Хороший пример — генератор обхода дерева из топика Iterators & Generators:

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

Выглядит понятно и логично — возвращаем элементы левой ветки, потом корень, потом элементы правой ветки. Класс.

Функциональные генераторы не могут продолжать выполнение кода после оператора return, каждый вызов итератора приводит к выполнению функции с начала. Поэтому состояние приходится сохранять в переменных, замкнутых на функцию-итератор.

Попробуем создать функциональный генератор рекурсивного обхода дерева.
Попытка 1, дублирование логики настоящего генератора:

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

Получилось так себе, но особенно печалят две вещи.

1. Наличие трех операторов return в теле итератора. В случае оператора yield все выглядит логично, поскольку выполнение продолжается со следующей строки. Однако если в качестве yield используется return, логика нарушается, и понять что происходит становится сложнее.

2. Пустое дерево на входе генератора обрабатывается отдельным пустым итератором return function () {}, что еще больше запутывает код.

Источником проблем в данном случае является копирование логики настоящего генератора, который умеет сохранять свое состояние. Чтобы код функционального генератора стал понятным, нужно сохранять состояние более явно.

Поразмышляем над итерацией по дереву.
Очевидно, что придётся оперировать итераторами по узлам левой и правой ветвей дерева.
Когда итератор левой ветви израсходован, нужно использовать корень, после чего использовать итератор правой ветви.
Если бы получилось представить корень в виде итератора, получилось бы три итератора, каждый из которых нужно последовательно изпользовать до конца, возвращая результат, после чего дерево будет пройдено полностью.

Попробуем воплотить в коде:
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();
        }
    };
}

Получилось почти хорошо — оператор return в итераторе один, а код итератора очень простой.

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

Управление итераторами


Особо дотошные ребята могли бы возразить мне еще в начале топика, например, так: «Постой-ка, ты говоришь, что итератор — это функция. Замечательно, но что ты будешь делать с этой функцией, если тебе потребуется сбросить состояние итератора?»

Отвечаю: я добавлю этой функции метод :) Функции в javascript — это объекты. Разумеется, функции могут иметь методы.

Старая добрая последовательность Фибоначчи, теперь с методом сброса:

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
}

Если использовать терминологию, то метод restart является привилегированным, что фактически означает наличие замыкания на внутренние переменные итератора.
Аналогичным образом можно дополнить итератор любыми необходимыми методами, влияющими на его внутреннее состояние.

Выводы


Итераторы и генераторы в виде паттернов проектирования неплохо приживаются в javascript благодаря гибкости его функций. Разумеется, функциональные итераторы уступают по производительности настоящим итераторам, но в местах, где производительность не важна, использование функциональных итераторов может упорядочить и упростить код.

Благодарю за внимание!
Tags:
Hubs:
+34
Comments 9
Comments Comments 9

Articles