[CPS変換]継続ってパイプライン的な何かだなと思ったらなんかわかってきたの続きです。
CPS 変換から継続モナドへの記事を読んでいたらまた何か急にわかってきたので書いてみました。
まとめ：パイプラインの中で分岐ができます。 すごい!
なるべく簡単にして自分がわかるようにするためのメモ的なものです。
正しくは元記事を御参照ください。
パイプライン的に話を進めるために、まずは簡単なパイプライン関数を作ります。
const pipe = x => f =>
typeof f !== "function"
? x
: pipe(f(x))
// 使用例：
pipe( 1 )
( x => x + 1 )
() // 2
値をいれものに入れる関数 ret
const ret = x =>
k => k(x)
値を 継続スタイルで使う「いれもの」に 入れます。
「いれもの」っていっても外見は関数(クロージャ)です。
内部に 値x を隠し持っていて、値x に適用する関数 k を欲しがってる関数です。
次の関数kは、値をとって関数を欲しがって、値に何らかの処理を施した上で関数に適用しようとする関数(継続っていう)でもいいし、単純に普通の、値をとって何か値を返す関数でもokです。
いれものから値を取り出す関数 evalCont
const evalCont = c =>
c(x=>x)
「いれもの」に 恒等関数を適用することで内部に隠してあった値を曝すことができます。
関数を適用する関数 bind
const bind = k => c =>
m => c(x => k(x)(m))
- 継続
kと いれものcを取って、 - つぎの関数
mを欲しがって - いれもの
cに 内部の値xにkを適用してからmを適用する関数を 与える
ってイメージでしょうか。
使ってみる
// 直接：
(x => x + 1)(1) // 2
// CPS:
evalCont(
bind( x => ret(x + 1) )( ret(1) )
) // 2
// パイプライン：
pipe( ret(1) )
( bind( x => ret(x + 1)) )
( evalCont )
() // 2
現在の継続を取り出す関数 callCC
const callCC = f =>
m => f(x => _ => m(x))(m)
// 使用例：
const f = x => {
if (x == 0) return "zero";
return "non-zero";
}
f(0) // 'zero'
f(1) // 'non-zero'
const g = x =>
pipe( callCC( exit => pipe( x === 0 ? exit("zero") : ret() )
( bind( _ => ret("non-zero")) )
()
)
)
( evalCont )
()
g(0) // 'zero'
g(1) // 'non-zero'
ちょっと変形してみます。
const callCC = f =>
m => f( jumpTo(m) )( m )
const jumpTo = m =>
x => _ => m(x)
こうしてみると、callCC の引数 関数fの引数exitは何か謎の引数ではなく、jumpTo(m)だってことがわかります。
これに何か値(例では"zero")を与えると、自分の継続を無視して値をcallCCの継続に適用しようとする特別な いれもの_ => m(x)ができます。
これと普通のいれもの(例ではret())とを条件で選んでbindに送るとあら不思議。bindが作用したりしなかったり...っていう仕掛けでしょうか。
実際にbindに_ => m(x)を渡してみると：
bind(k)(_ => m(x))
>>> m_ => (_ => m(x))(x=>k(x)(m_))
>>> m_ => m(x)
ここでm_はbindの継続、mはcallCCの継続です。ややこしい。
何か関数を欲しがって、でも与えられたらそれは捨てて、calCCの継続に値を適用しようとする いれもの ができあがります。_ => m(x)と同じです。なので以降のbindにも作用しません。
callCCから出ると：
callCC( _ => m(x) )
>>> m => ( _ => m(x) )(m)
>>> m => m(x)
と、また普通の いれもの になり、bindも作用するようになります。
例えばこんな動作です。
const g = x =>
pipe( callCC( exit => pipe( x === 0 ? exit(x) : ret(x) )
( bind( x => ret(x + 1)) )
( bind( x => ret(x + 1)) )
()
)
)
( bind( x => ret(x + 1)) )
( evalCont )
()
g(0) // 1
g(1) // 4
0のとき、callCC内部のbindは作用してませんが、外のbindは作用しています。
使ってみる
以上を全部使って、継続渡しスタイルでフィボナッチ関数を書いてみます。
const fibCPS = n =>
callCC( exit => pipe( n < 2 ? exit(1) : ret() )
( bind(_ => ret(n - 2)) )
( bind( fibCPS ) )
( bind(a => pipe( ret(n - 1) )
( bind( fibCPS ) )
( bind(b => ret(a + b)) )
()
)
)
()
)
// 使用例：
pipe( ret(5) )
( bind(fibCPS) )
( evalCont )
() // 8
あるいは短かくしたければこれでもよい。同じことです。
const fibCPS = n =>
callCC( exit => pipe( n < 2 ? exit(1) : fibCPS(n - 2) )
( bind(a => pipe( fibCPS(n - 1) )
( bind(b => ret(a + b)) )
()
)
)
()
)
// 使用例：
pipe( fibCPS(5) )
( evalCont )
() // 8
// あるいは：
evalCont(fib(5)) // 8
理屈がわかっていればこれも可能：
const fibCPS = n =>
callCC( exit => pipe( n < 2 ? exit(1) : fibCPS(n - 2) )
( bind(a => fibCPS(n - 1)
(b => ret(a + b))
)
)
()
)
// 使用例：
fib(5)(x => x) // 8
pipe、bindが要るところ/要らないところ、evalContが効くところ/効かないところがでてきてしまうのでおすすめはできませんが。
ただ、動作は速い感じです。
もっとお手軽にしてみる
pipe、ret、bind、callCCの合わせ技で分岐ができるっていうのはわかりました。でも、もっとお手軽なのがいいな...というわけで、もっと簡単にできないか考えてみました。
...長くなったので続きは次の記事で。