遅延リストを扱うライブラリと Stage 2 Iterator Helpers
イテレーターのインターフェースについて
ES2015 から Iterable
インターフェースを実装したオブジェクトに対して for-of
やスプレッド構文を使うことが出来ます。インターフェースについて詳しくは qnighy さんの記事を御覧ください。
遅延リストを扱うライブラリ
整数が入った配列があったとします。その配列に対して要素を二乗し、一つ足し、その後で偶数のみを取り出すことを考えます。愚直に実装すると以下のようになります。
const arr = [];
for (let i = 0; i < 100000; ++i) {
arr[i] = i;
}
const result = arr
.map((val) => val * val)
.map((val) => val + 1)
.filter((val) => val % 2 === 0);
この実装には問題があります。Array#map
は配列から新しく配列を作るメソッドなので、その度にヒープメモリを確保し消費してしまいます。パフォーマンスが良くありません。
この問題に対処する一つの方法が lazy に実行することです。最後に必要になるまで配列を作らなければ、無駄なメモリ使用を防ぐことが出来ます。
itertools.js
Python の itertools を JavaScript にポートしたライブラリがあります。ジェネレーター函数を使って実装されています。
函数の先頭に i がついているものは IterableIterator
(Generator
) を返し、そうでないものは配列を返します[1]。
import { imap, filter } from "itertools";
const arr = [];
for (let i = 0; i < 100000; ++i) {
arr[i] = i;
}
const result =
filter(
imap(
imap(
arr,
(val) => val * val,
),
(val) => val + 1,
),
(val) => val % 2 === 0,
);
Lazy.js
JavaScript にまだイテレーターがなかった時代に作られた Lazy.js というライブラリがあります。独自に Sequence
クラスを実装して作られています。
import Lazy from "lazy.js";
const arr = [];
for (let i = 0; i < 100000; ++i) {
arr[i] = i;
}
const result = Lazy(arr)
.map((val) => val * val)
.map((val) => val + 1)
.filter((val) => val % 2 === 0)
.toArray();
IxJS
Push-based Streams のための RxJS は有名ですが、それとは対照的に Pull-based Streams のための IxJS があります。独自に IterableX
クラスを実装して作られています。
import { from, toArray } from "ix/iterable";
import { map, filter } from "ix/iterable/operators";
const arr = [];
for (let i = 0; i < 100000; ++i) {
arr[i] = i;
}
const result = toArray(
from(arr).pipe(
map((val) => val * val),
map((val) => val + 1),
filter((val) => val % 2 === 0),
),
);
Stage 2 Iterator Helpers
%IteratorPrototype%
と %AsyncIteratorPrototype%
に新たにメソッドを追加する提案が Stage 2 Iterator Helpers です。
const arr = [];
for (let i = 0; i < 100000; ++i) {
arr[i] = i;
}
// Array#values で Iterator クラスを継承したインスタンスを作る
const result1 = arr.values()
.map((val) => val * val)
.map((val) => val + 1)
.filter((val) => val % 2 === 0)
.toArray();
// もしくは Iterator.from で Iterator クラスを継承したインスタンスを作る
const result2 = Iterator.from(arr)
.map((val) => val * val)
.map((val) => val + 1)
.filter((val) => val % 2 === 0)
.toArray();
%IteratorPrototype%
インターフェースと for-of
やスプレッド構文については Iterable
インターフェースを実装していれば使うことが出来ました。しかしこの提案のメソッドは Iterator
インターフェースだけでは不十分で、プロトタイプチェーンの中に %IteratorPrototype%
がないと使うことが出来ません。
もしジェネレーター函数を使わずに独自で Iterator
インターフェースを実装している場合はグローバルの Iterator
クラスを継承する必要があります。
class MyIterator extends Iterator {
next() {}
return() {}
throw() {}
}
もしくはメソッドを使う直前に Iterator.from
を使って変換するのもいいでしょう[2]。
%IteratorHelperPrototype%
Iterator Helpers のメソッドを使った場合、単純に [[Prototype]]
に %IteratorPrototype%
(Iterator.prototype
) を持つインスタンスではなく、更にもう一段階ラップした %IteratorHelperPrototype%
を持つインスタンスを返すようになっています[3]。
これは元々のインスタンスに return
や throw
メソッドが定義されていた場合に、それがちゃんと受け継がれるようにするためだと考えられます。
イテレーターの再利用不可能性
注意点として Iterator Helpers のメソッドではイテレーターの再利用ができません。
const arr = [];
for (let i = 0; i < 100000; ++i) {
arr[i] = i;
}
const iterator = arr.values()
.map((val) => val * val)
.map((val) => val + 1);
// この Iterator#toArray で iterator を完了状態にする
const mapped = iterator.toArray();
// iterator は既に完了しているため、空配列になってしまう
const filtered = iterator
.filter((val) => val % 2 === 0)
.toArray();
console.assert( filtered.length === 0 );
これは Lazy.js や IxJS とは異なる特徴です。Lazy.js や IxJS では独自クラスの中にそのソースとなる配列への参照を保持しているため、何度でも toArray
によって配列を作ることが出来ます[4]。一方でネイティブの Iterator
クラスではそれが出来ません。
これが問題になることはあまりないと思いますが、また同様の手順でイテレーターを作るか、一旦配列にしてしまうかなどして対処する必要があります[5]。
関連する提案
Iterable
インターフェースを実装したオブジェクトから配列を作るには Array.from
がありますが、AsyncIterable
インターフェースから配列を作る函数は今のところありません。このミッシングピースを埋める提案が Stage 1 Array.fromAsync
です。
const asyncIterable = (async function*() {
for (let i = 0; i < 10; ++i) {
yield i;
}
})();
const arr = await Array.fromAsync(asyncIterable);
結び
今回は Iterator Helpers を紹介してみました。便利ではあるんですが、ただでさえ複雑な JavaScript のイテレーター周りの仕様が更に複雑になりそうな印象を受けますね。
今までは Iterator
と言うとそのインターフェースを意味していましたが、今後は Iterator
クラスのことを意味するようになるかもしれません。TypeScript の型定義はいったいどうなるんでしょうか……。
ECMAScript の提案を追うのは割と楽しいので皆さんもよかったらどうぞ。
-
どうでもいいんですが
imap
という函数名だとメールのプロトコルを連想しますよね。 ↩︎ -
Promise.resolve
を使ってThenable
をPromise
化するのに似ています。 ↩︎ -
Iterator.from
函数を使った場合にその引数がIterator
クラスを継承したインスタンスでない場合は[[Prototype]]
に%WrapForValidIteratorPrototype%
を持つインスタンスを返すみたいです。複雑ですね。 ↩︎ -
厳密には IxJS の
from
函数にはIterable
だけではなく、Iterator
インターフェースを実装したオブジェクトを突っ込むことができ、そのような場合についても再利用できません。 ↩︎ -
Iterator Helpers に
Iterator
クラスのインスタンスを複製するtee
メソッドが欲しいところではありますがそれはうまくいきません。素朴に一方のIteratorResult
をキューにためておいて他方で再利用する実装が思いつきますが、next
メソッドに引数を入れた場合や、return
やthrow
メソッドの扱いなどを考えると難しいことがわかります。 ↩︎
Discussion
これは遅延評価ではなく、「遅延リスト」や「ストリーム」のような表現が正しいです。遅延評価は評価戦略の話であり、ESの評価戦略は遅延評価ではありません。
ご指摘ありがとうございます。記事も読まさせていただきました。
https://bleis-tift.hatenablog.com/entry/20130102/1357062031確かに問題がありそうだと思ったため修正しました。
JavaScript の世界で単に「ストリーム」という言葉を使うと WHATWG Streams など別のことを意味してしまいそうだったため、「遅延リスト」の方を選ばせていただきました。
一方で Lazy.js が
https://github.com/dtao/lazy.js#featuresと紹介されていたり、英語版の Wikipedia の Lazy evaluation には Simulating laziness in eager languages の例として JavaScript のジェネレーター函数の例
https://en.wikipedia.org/wiki/Lazy_evaluation#JavaScriptが載っていたりと広い意味での「遅延評価」という言葉が流通してしまっている感は否めない気がしますね……。