「計算論なんかチューリングマシンで十分だし、おれはチャーチじゃなくチューリングについていくぜ！Yコンビネータくそくらえ！」
という人もいるんじゃないでしょうか。
やっぱチャーチよりチューリングですよね。
という人のために、われらがチューリング先生がコンビネータを用意してくださっています。
Θ=(λx.λy.y(xxy))(λx.λy.y(xxy))
Groovyで書くとこうですね。
def th = {x -> {y-> y(x(x)(y))}}({x -> {y -> y(x(x)(y))}})
ためしにフィボナッチを。
> println th({f -> {n -> n < 2 ? n : f(n - 1) + f(n - 2)}})(7)
Exception in thread "main" java.lang.StackOverflowError
むむ、スタックオーバーフロー
ということで、遅延評価を込みこみます。
def th2 = {x -> {y-> y({m -> x(x)(y)(m)})}}({x -> {y -> y({m -> x(x)(y)(m)})}})
試してみます。
> println th2({f -> {n -> n < 2 ? n : f(n - 1) + f(n - 2)}})(7)
13
やりました！
Yコンビネータを使わなくても、λによる再帰ができました。
これで、もう一生Yコンビネータなぞに煩わされずにすみます。
ありがとうチューリング先生！
