ymyzk’s blog

ECMAScript 6 でジェネレータを作ったり、遅延評価してみる

—

by

Yusuke Miyazaki
in

「Ruby の Enumerator でジェネレータを作ったり、遅延評価してみる」や「Python でジェネレータを作ったり、遅延評価してみる」の記事を ECMAScript 6 のジェネレータを使って記述するとどのようになるのか, 実際に試してみました.

ECMAScript 6

ECMAScript 6 の各ブラウザや処理系での実装状況の詳細はこちらを参照してください.

現時点でこの記事のコードがそのまま実行できる処理系はないと思われます. コードを Babel 等を用いて ECMAScript 5 のコードに変換するか (この場合ジェネレータを利用するために Polyfill が必要になります) arrow functions などの処理系が対応していない部分を書き換えて実行する必要があります.

ジェネレータの基本

ECMAScript 6 で提案されているジェネレータについては「function* – JavaScript | MDN」などを参照してください.

ジェネレータ関数の書き方は Python のものと非常によく似ていますが, 通常の関数は function で記述するのに対し, ジェネレータ関数は function* で記述します. (Python の場合はどちらも def で良い.)

(function() {
  "use strict";

  function* generator() {
    yield 1;
    yield 2;
    yield 3;
  }

  var g = generator();
  g.next();  // { value: 1, done: false }
  g.next();  // { value: 2, done: false }
  g.next();  // { value: 3, done: false }
  g.next();  // { value: undefined, done: true }


  for (let i of generator()) {
    console.log(i);  // 順に 1, 2, 3 が表示されます
  }
})();

フィボナッチ数列のジェネレータ

例としてフィボナッチ数列のジェネレータを作成します. fib_generator はフィボナッチ数列を無限に返すジェネレータ関数です.

(function() {
  "use strict";

  var fib_generator = function* () {
    var a = 0, b = 1;
    while (true) {
      yield a;
      [a, b] = [b, a + b];
    }
  };

  var fib = fib_generator();
  console.log(fib.next());  // { value: 0, done: false }
  console.log(fib.next());  // { value: 1, done: false }
  console.log(fib.next());  // { value: 1, done: false }
  console.log(fib.next());  // { value: 2, done: false }
  console.log(fib.next());  // { value: 3, done: false }
})();

遅延評価

yield を使ったジェネレータ関数を用いると遅延評価を実現できることは, これまでの例から分かることと思います. ジェネレータ関数を呼び出すとイテレータオブジェクトが返されますが, イテレータに対して処理を行いその結果をイテレータとして返す関数を利用することで, より複雑な処理を行うことができます.

Python の場合はこのような処理は itertools でこのような関数が提供されていますが, ECMAScript にはそれに対応するものは標準で存在しません. 類似のものに Array.prototype.filter や Array.prototype.map があり, これと同様の操作をイテレータにおいても模倣してみたいと思います.

実際の例を以下に示します.

(function() {
  "use strict";

  var GeneratorFunction = ((function* () {})()).constructor;

  GeneratorFunction.prototype.map = function* (callback, thisArg) {
    var i = 0;
    var o = Object(this);
    for (let item of this) {
      yield callback.call(thisArg, item, i, o);
      i++;
    }
  };

  GeneratorFunction.prototype.filter = function* (callback, thisArg) {
    var i = 0;
    var o = Object(this);
    for (let item of this) {
      if (callback.call(thisArg, item, i, o)) {
        yield item;
      }
      i++;
    }
  };

  GeneratorFunction.prototype.take = function* (n) {
    for (let item of this) {
      if (n <= 0) {
        break;
      }
      yield item;
      n--;
    }
  };

  var fib_generator = function* () {
    var a = 0, b = 1;
    while (true) {
      yield a;
      [a, b] = [b, a + b];
    }
  };

  // console.log(Array.from(fib_generator()));
  // 停止しない

  console.log(Array.from(fib_generator().take(10)));
  // [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ]

  console.log(
    Array.from(fib_generator().map(x => Math.pow(x, 2)).take(10)
  ));
  // [ 0, 1, 1, 4, 9, 25, 64, 169, 441, 1156 ]

  console.log(
    Array.from(fib_generator().map(x => Math.pow(x, 2)).filter(x => x % 2 === 1).take(10)
  ));
  // [ 1, 1, 9, 25, 169, 441, 3025, 7921, 54289, 142129 ]
})();

50-52 行目の例ではフィボナッチ数列の各要素を2乗したものを, 先頭から10個取得する例です. まずフィボナッチ数列を返すイテレータを作り, そこから map を用いてフィボナッチ数列の各要素を2乗したものを返すイテレータを生成します, さらにイテレータの先頭から10要素だけ返すイテレータを生成します. 最後に Array.from で Array に変換してから表示しています.

55-57 行目の例はもう少し複雑な例で, フィボナッチ数列の各要素を2乗したものから, 奇数の要素だけの数列を作り, 先頭から10個取得する例です.

ジェネレータ関数が返すイテレータオブジェクトは map や filter を実装していないため, これらは 6-34 行目で独自に実装しています. ここでの map や filter の実装は Array.prototype.map や Array.prototype.filter の実装を簡略化したものとしています.

ジェネレータについてのクラス図を見ると, ジェネレータ関数が返すイテレータオブジェクトは GeneratorFunction のインスタンスとなっています. このため GeneratorFunction の prototype に map や filter を実装すれば良いことがわかります.

しかし GeneratorFunction は global name を持たないため, これの prototype を直接編集することはできません. そこで4行目のように空のジェネレータを作成してその constructor を取得して, GeneratorFunction への参照を得ています.

参考

この記事の内容について検討するにあたり @tyage に助言を頂きました. 感謝.

更新

  • 2015/4/26 ジェネレータについてのクラス図を最新のものに更新

関連