Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

Yコンビネータ

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

で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")