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)