Y combinator: フィボナッチ数

Y combinatorを使ってフィボナッチ数を求めてみる。

fib0 = lambda {|f|
  lambda {|n|
    (n == 1) ? 1 :
    (n == 2) ? 1 :
    f.call(n - 2) + f.call(n - 1)
  }
}

y = lambda {|f0|
  lambda {|f|
    f0.call(lambda {|arg| f.call(f).call(arg)})
  }.call(
    lambda {|f|
      f0.call(lambda {|arg| f.call(f).call(arg)})
    }
  )
}

puts y.call(fib0).call(5) # => 5

ふむふむ。