Y Combinator

仕事でRailsにどっぷり漬かりそう(それはそれで楽しいけど)なので、彼方に行き過ぎないよう、いままで見て見ぬ振りをしてきたY Combinator(不動点コンビネータともいうの？)を見てみることにする。

以下、どう書く？org から引用

# let rec y f x = f (y f) x;;
val y : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
# let fact = y (fun f x -> if x=0 then 1 else x * (f (x-1)));;
val fact : int -> int = <fun>
# fact 10;;
- : int = 3628800

＃その他、nanigac.com も。

まず、factが自分自身を呼び出していないことに驚く。

yは受け取った関数を再帰的に呼び出しているみたいだが…
xが引数としてついているので、factの定義時にいきなり評価されることは無いみたいだが…
結局のところ、完全にはわからん…

プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~

に載っていた I or K Combinator は簡単だったのになぁ…

まぁ、理論をすっとばしておいて勝手に愚痴る者、の図でした。