再帰関数の表現

let a = v; restは(\a -> rest)(v)と等価だけど、再帰関数はどうなるか。

まず、Y f -> bodyを用意する。Yは、引数にfを受け取り、fはbody中に出てきてもよくて、その場合bodyになる、ようなbodyをつくる式。

こうすると、

  • letrec f(x) -> body; rest => (\f -> rest)(Y f -> \x -> body)

ちなみに、値の再帰定義もYで可能(andやorのような遅延評価構造がないと実行で無限ループする)

  • letrec x = v; rest => (\x -> rest)(Y x -> v)