Rubyで無名再帰(Zコンビネータ) #Ruby

無名再帰を使ってフィボナッチ数の計算をしてみた。
イマイチ理屈はわかってないけど…

z-combinator.rb

# Zコンビネータ
def Z(func)
  lambda do |f|
    lambda{|x|lambda{|y| f[x[x]] [y]}}[
      lambda{|x|lambda{|y| f[x[x]] [y]}}]
  end[func]
# .callメソッドで書くとこう
#  lambda do |f|
#    lambda{|x|lambda{|y| f.call(x.call(x)).call(y)}}.call(
#      lambda{|x|lambda{|y| f.call(x.call(x)).call(y)}})
#  end.call(func)
end

# フィボナッチ数
fib = Z(lambda{|f|lambda{|n| n < 2 ? n : f[n - 2] + f[n - 1]}})
p fib.call(7) # 1, 1, 2, 3, 5, 8, 13, ...

とりあえず今はおまじない的に覚えておこうと記録