Yコンビネータ

相変わらず，Yコンビネータについては理解できていないのですが，昨日に引き続き，Rubyの学習もかねて，Schemeで書かれたYコンビネータをRubyで書くことに挑戦しました。

• http://d.hatena.ne.jp/kazu-yamamoto/20080402/1207127522

でYコンビネータは，以下のように紹介されています。

(lambda (le)
  ((lambda (f) (f f))
   (lambda (g) (le (lambda (x) ((g g) x))))))

昨日は，たくさん出てくるlambdaをRubyでどう書けば良いのか分からなかったのですが，今日はなんとかYコンビネータをRubyで書くことができました。

y = lambda { |le|
  lambda { |f|
    f.call(f)
  }.call(
    lambda { |g|
      le.call(lambda { |x| g.call(g).call(x)})
    }
   )
}

fact = lambda { |f|
  lambda { |n|
    if n == 0
      1
    else
      n * f.call(n - 1)
    end
  }
}

puts y.call(fact).call(5)      # 5!

あまりにもYコンビネータが不思議で面白いので，"Ycombinator".length と書けばいいようなものも書いてみました(↓)。

len = lambda { |f|
  lambda { |str|
    if str == ""
      0
    else
      1 + f.call(str.chop)
    end
  }
}

puts y.call(len).call("Ycombinator")