先に結論
できる。というか、遅延リストじゃん、これ
例えば、次のようなコードで、非負偶数を無限にコンソールに出力できる。
const arith = (a, d) => () => GMore(a, arith(a + d, d));
for (const x of gRun(arith(0, 2))) console.log(x);
// 0
// 2
// ...
トランポリンのおさらい
三角数(1 ~ n の総和)を求める関数を、次のような再帰関数で実装したとする。
const rTri = n => _rTri(n, 0);
const _rTri = (n, acc) =>
n <= 0 ? acc : _rTri(n - 1, acc + n);
すると、大きな値を渡した瞬間スタックオーバフローで落ちる1
rTri(10000); // 50005000
rTri(100000); // スタックオーバフロー
どうにか再帰関数っぽく書きつつスタックオーバーフローを避けることはできないのか?
そこで颯爽と登場するのがトランポリンである。トランポリンを実現する関数は、例えば次のように実装できる。
const TDone = value => (f, _) => f(value);
const TMore = more => (_, f) => f(more);
const tRun = more => {
let done = false;
let value;
while (!done) {
more()(
v => {done = true; value = v;},
m => {more = m;}
);
}
return value;
};
さっそく三角数を求める関数をトランポリンで実装してみる。
どでかい値を渡しても正しい値が返ってくる。
成功だ、_tTri
は自分自身を呼び出し再起しているが、スタックオーバーフローはしない
const tTri = n => tRun(_tTri(n, 0));
const _tTri = (n, acc) => () =>
n <= 0 ? TDone(acc) : TMore(_tTri(n - 1, acc + n));
tTri(10000); // 50005000
tTri(100000); // 5000050000
tTri(1000000); // 500000500000
これがトランポリンの魔法である。魔法の中身については、他の記事に譲ろう。「トランポリン」の検索結果 - Qiita。
ジェネレータ関数のトランポリン
0 ~ n-1 番までの三角数を生成するジェネレータ関数を、次のような再帰ジェネレータ関数で実装したとする。
const rTriGen = n => _rTriGen(n, 0, 0);
const _rTriGen = function* (n, i, acc) {
if (n <= i) return;
yield acc;
yield* _rTriGen(n, i + 1, acc + i + 1);
};
すると、大きな値を渡した瞬間スタックオーバフローで落ちる。
[...rTriGen(10)];
// [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
for (const x of rTriGen(100001)) {}
// スタックオーバーフロー
さて、通常の再帰関数と同じように、ジェネレータ再起関数もトランポリンによってスタックオーバーフローを避ける(スタックレスにする)ことはできるのだろうか?
通常の再起関数と、ジェネレータ再起関数の違いは値を返却するタイミングである。
- 通常の再帰関数:再起が終了した最後に値を返却する
- ジェネレータ再帰関数:再起するたびに値を返却する。
上記を考慮して通常のトランポリンを、うまいことジェネレータ関数用のトランポリンに書き直せばよさそうだ。早速、やってみよう。
const GDone = () => (f, _) => f();
const GMore = (value, more) => (_, f) => f(value, more);
const gRun = function* (more) {
let done = false;
let value;
for (;;) {
more()(
() => {done = true;},
(v, m) => {value = v; more = m;}
)
if (done) return;
yield value;
}
};
0 ~ n-1 番までの三角数を生成するジェネレータ関数をトランポリンで実装してみる。
どでかい値を渡しても正しい値が返ってくるようになった。
成功だ、_gTri
は自分自身を呼び出し再起しているが、スタックオーバーフローはしない
const gTri = n => gRun(_gTri(n, 0, 0));
const _gTri = (n, i, acc) => () =>
n <= i ? GDone() : GMore(acc + i, _gTri(n, i + 1, acc + i));
[...gTri(10)];
// [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
let x;
for (x of gTri(100001)) {}
x; // 5000050000
結論
できる。
おまけ:遅延リスト
誤解を恐れずに言えば、GDone
は遅延リストのNil
、GMore
は遅延リストのCons
と読み替えられる。
// [1, 2, 3]
[...gRun(() => GMore(1, () => GMore(2, () => GMore(3, () => GDone()))))]
// 初項 a 、公差 d の等差数列
const arith = (a, d) => () => GMore(a, arith(a + d, d));
// 各項に関数 f を適用した新たな列を得る
const gMap = f => more => () => more()(
() => GDone(),
(v, m) => GMore(f(v), gMap(f)(m))
);
// 最初の 0 ~ n - 1 項を取得する
const gTake = n => more => () => n <= 0 ? GDone() : more()(
() => GDone(),
(v, m) => GMore(v, gTake(n - 1)(m))
);
// 0 ~ 9 項までの非負偶数
// [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
[...gRun(gTake(10)(arith(0, 2)))]
// 0 ~ 9 項までの非負偶数の自乗数
// [0, 4, 16, 36, 64, 100, 144, 196, 256, 324]
[...gRun(gTake(10)(gMap(x => x * x)(arith(0, 2))))]
以上
-
末尾再帰最適化が有効な場合は、スタックオーバーフローしないが、ここでは無効なものとする ↩