継続って何かわかりにくいんですよ。で、こちらの記事「CPS 変換による末尾再帰化」を読んでたら、なんとなくわかったような気がしてきて、アロー関数で書いてみたらどうかなーとかやってたら何か急にわかってしまいました。
まとめ： 継続は、パイプライン的な何かです。
以上。「そんなの知ってたよ」って方は生暖い目で見てやってください。
何言ってるのかわからないかも知れませんが、元記事を参照していただければわかるかも知れません。
継続スタイルに変換する関数
を考えてみました。関数f、fの引数x、継続kとして
const cpsfy = f => x => k =>
k(f(x))
f を適用してから k を適用するっていう何か関数合成的なやつですね。
f、x を部分適用すると「x に f を適用してある値になったのだが、さらに次の関数 k を欲しがってる」状態になります。
k は 継続スタイルの関数でも通常の関数でもOKです。継続なら後にもうひとつ関数を欲しがり、通常ならその関数が適用されて値になります。
使ってみる
このあと使うので、恒等関数を継続スタイルにしてみます。
// 恒等関数：
const id = x => x
// 継続スタイルにする：
const idCPS =
cpsfy(id)
同様に、インクリメントを継続スタイルにしてみます。
const inc = x => x + 1
const incCPS =
cpsfy(inc)
使ってみます。同じことをやっています。
// 直接スタイル：
inc(inc(inc(1))) // 4
// 継続スタイル：
idCPS(1)(incCPS)(incCPS)(incCPS)(id) // 4
1 を 3 回インクリメントして 4 になる、という同じことをやっています。
継続の方は何か面倒なことになっていますが、idCPS で 1 を継続に「持ち上げ」て、incCPSで三回インクリメントして、 id で値にする、といった意味です。
idCPSとidの間に継続をパイプライン的に繋げて使うことができます。
階乗
idCPS と cpsfy を使って継続にします。
// 直接：
const fact = n =>
n <= 1
? 1
: fact(n - 1 ) * n
// 継続：
const factCPS = n => k =>
n <= 1
? idCPS(1)(k)
: idCPS(n - 1)(factCPS)(cpsfy(v => v * n))(k)
idCPS(5)(factCPS)(id) // 120
idCPS(n - 1)(factCPS)(cpsfy(v => v * n))(k) の部分が肝です(キモくもある?)。
「n-1 を 階乗にして n と掛けて k する」って見えてきませんか?ほーら見えてきた!
...順番に見えるようにわざと長たらしく書いています。短かく書くと :
factCPS(n - 1)(v => k(v * n))
ってことです。簡潔、これでよい。
だけど継続っぽくはないよね。なので：
-
factCPS(n - 1)をidCPS(n - 1)(factCPS)に -
(v => k(v * n))を(cpsfy(v => v * n)(k))に- 更に
(cpsfy(v => v * n))(k)に
- 更に
最後のかっこの外に出すやつは、別にそんな理論があるわけではないのですが、意味的に、継続でパイプライン的に順番に関数適用していく、という風に考えると、結局同じことじゃね? ということでやってます。
フィボナッチ数列
// 直接：
const fib = n =>
n < 2
? 1
: fib(n - 2) + fib(n - 1)
// 継続：
const fibCPS = n => k =>
n < 2
? idCPS(1)(k)
: idCPS(n - 2)(fibCPS)(a =>
idCPS(n - 1)(fibCPS)(cpsfy(b => a + b))
)(k)
idCPS(5)(fibCPS)(id) // 8
idCPS(n - 2)(fibCPS)(a => idCPS(n - 1)(fibCPS)(cpsfy(b => a + b)) )(k) は：
- n-2 をフィボナッチ数にして a とし、
- n-1 をフィボナッチ数にして b とし、
- a と b を足して、
- k する
という意味です。ちゃんと順番通り。
末尾再帰
ちなみにこんな風にしたら大きい数でも「RangeError: Maximum call stack size exceeded.」がでないで計算してくれるようになった(時間はかかるけど)。理由はわからん。
// 元記事より。エラー。
> function fibCPS(n, k) {
if (n <= 2) {
k(1);
} else {
fibCPS(n - 2, a =>
fibCPS(n - 1, b =>
k(a + b)));
}
}
fibCPS(21,x=>x)
< RangeError: Maximum call stack size exceeded.
// この記事のやつ。エラーにならなかった。
> const fibCPS = n => k =>
n < 2
? k(1)
: idCPS(n - 2)(fibCPS)(a =>
idCPS(n - 1)(fibCPS)(cpsfy(b => a + b))
)(k)
idCPS(40)(fibCPS)(id)
< 165580141
safari の JavaScriptコンソールにて。
以上です。
あくまで独自見解なので「おかしくね?」っていうところあればコメントよろしくです。