ArrowのloopとYコンビネーター - takkan

言語ゲーム - ArrowLoopで、ArrowのloopでYコンビネーターができるというので、ちょっと試してみた。

Arrowのloopは以前、MaDさんの記事でなんとなく、理解をしていたつもりだったんだけど、実際に自分で書いてみると全然わかっていない、Haskell(主に、if式とlet式)理解していないことをあらためて感じた。

僕の中で、Yコンビネーターといえば、階乗計算なので、階乗計算を書いてみる。
まずは、id:propellaさんのcountdownを真似てみる。

fact (a,f) = ( f a , fc)
    where
        fc 1 = 1
        fc x = x * f (x-1)

loop fact 10

fcという名前がなんとなく、嫌なのでfcを無名関数で記述。

fac (x,f) = (f x, (\y -> if y == 1 then 1 else y*(f (y -1))))
loop fac 10

こう書いたところで、実際にloopに対して渡す引数に、計算するときにfacの引数のタプルのxの部分にしか、値を渡さないのに、なぜfacが返すタプルのfstとsndでloopに渡していないfを利用できるのかが分けわからなくなる。

なので、loopの定義を思い出して追っかけてみる。

loop f b = let (c,d) = f (b,d) in c  -- loopの定義
loop fac 2 --　大きい数だと簡約の段数が多くなるので、2に
let (c , d ) = fac (2 , d ) in c -- 計算の結果として　ｃが欲しいのでcを求めていく
let (c,d) = ( d 2 , (\y -> if y == 1 then 1 else y*(d (y-1)))) in c
-- 上記よりdは(\y-> if y == 1 then 1 else y * (d (y-1))))となるが、ここのdは遅延評価で簡約(?)されないのが重要
-- cを求めるためにd 2を簡約
let (c,d) = ( 2 * (d (2 -1)) ,(\y -> if y == 1 then 1 else y*(d (y-1)))) in c
-- cを求めるためにd (2-1)を簡約。dは上と同じ
let (c,d) = (2 * 1, (\y -> if y == 1 then 1 else y*(d (y-1)))) in c
let (c,d) = (2,(\y -> if y == 1 then 1 else y*(d (y-1)))) in c
-- これでcが求まるので
2

これで、あっているのかなぁ。簡約という言葉の使い方が間違っている気もするしなぁ。

あらためて、遅延評価難しいと思った。d 2を簡約するときに同時にタプルのsnd側のdも置き換えたくなるもんなぁ。

こうなったら、階乗計算を一行で書きたくなったので、すべて無名関数に

fac = loop (\(x,f)->(f x,(\y->if y == 1 then 1 else f (y-1))))

最初は、loopなんて使って再帰書くよりも、ふつうに再帰使った方が早いよと思っていたんだけど、これを書いているうちに、loopはArrowなので、Arrowのストリームの中に、ループが埋め込まれるというのは、それはそれですっきりするような感じがしました。（なれるまでは、大変だけど)