Y Combinator

lambda

• 不動点演算子

• Y = \f.M_f = \f.(\x.f(xx))(\x.f(xx))

• ex. 階乗

  • f = \n.(if (n == 0) 1 (n * f(n - 1)))*

• Y combinatorを eta-conversion (M -> \x.Mx) したのが Z Combinator

  • CBNでないと無限ループしてしまうため
  • 再帰型が無いと型つけ出来ない
    • : a = a -> (int -> int)

参考文献

• ラムダ計算と再帰
• 不動点とfix演算子 - 一歩前進
• ocaml-zippy-tutorial-in-japanese/y.md at master · camlspotter/ocaml-zippy-tutorial-in-japanese · GitHub
  • 再帰型を再帰データ型 roll/unroll でencodingするのわかってない toohard