メモ - Y combinator (追記アリ - というか本エントリに載っているのはちょと違う)

@camlspotterさんありがとうございました。私が悪い頭をグルグル回している間も@_2F_1は沈黙を守っていました。きっかけはPythonで書かれたやつでした。これ使えば全てのループ処理がcall/ccみたいなので書けてスタック気にしなくてよくなるとかそういう世界だと思ってたんだけど全然理解できねー。なので図々しく教わりました。というわけでコード

let f fact x = if x=1 then 1 else x*fact(x-1) in
let ff fib x = if x<2 then 1 else fib(x-1)+fib(x-2) in
let rec y f x = f (y f) x in
let z = y f 10
and zz = y ff 10;;

昨日覚えたことからするとどっちも遅いけど、不動点を定義するらしい。なんか線形代数の固有ベクトルとか固有値の対角行列とか思い出した。つーときっと圏論とかそっちの話に入っていくんだろなと思って挫折。ラムダ式で書くとY combinator、

Y = \f. ( \x. f( x x ))( \x. f( x x ))

とはつまりこれらしい。
see pp.65

Types and Programming Languages

それでまあふと思い立ってErlangで書いてみたら全然動かない

-module(bad_ycombinator).
-compile(export_all).

f(_, 1)-> 1;
f(Fact, X)-> X * Fact(X-1).
  
y(F, X)-> F( y(F, X), X).

do(X)-> y( fun f/2 , X).

よくわからないけど高階関数の扱いがOCamlやHaskellと違うところでしくじっているように見える。カリー化するためには、変数を部分的に入れるだけじゃなくてそれ用のコードを書かないといけない。と思ったら動いた。

-module(ycombinator).
-compile(export_all).

f(_, 1)-> 1;
f(Fact, X)-> X * Fact(X-1).
y(F)-> fun(X)->F( y(F), X) end.

do(X)-> (y( fun f/2 ))(X).

書いてる途中で微妙に無限ループなどに入ったりしていた（特に y(F, X)-> ... なんて定義したとき）ので、キーポイントは、fun f/2の中でFactが評価される前にXがguardで評価されて、それでうまく収束していくようになっているんだろうなぁと思ったり思わなかったり。うーん不思議だ。

-module(bad_ycombinator2).
-compile(export_all).

f(_, 1)-> 1;
f(Fact, X)-> X * Fact(X-1).
y(F)-> fun(X)->F( (y(F))(X), X) end.

do(X)-> (y( fun f/2 ))(X).

ちなみに昨日のTail Recursive Fibで書くと

# let f fib c p n = if n<2 then c else fib (c+p) c (n-1);;
val f : (int -> int -> int -> int) -> int -> int -> int -> int = <fun>
# let rec y f c p n = f (y f) c p n ;;
val y :
  (('a -> 'b -> 'c -> 'd) -> 'a -> 'b -> 'c -> 'd) -> 'a -> 'b -> 'c -> 'd =
  <fun>
# let z = y f 1 1 10;;
val z : int = 89
# 

yの型がめちゃくちゃキモいですね。まあタプルでひとつにまとめろっちゅー話ですが

追記 3/24 22:50

長くなったので別エントリにしました。