Rubyのある風景 - Y Combinator
再帰的な関数を作るときに関数に名前をつけずに定義するにはどうしたらいいのかというのが、Y Combinatorの中心的な話題です。 まずは、再帰の定番、階乗を計算する関数に登場願いましょう。 fact = lambda{|n| if n < 2 1 else n * fact[n - 1] end } puts fact[10] ここからfactという名前を取り除こうというわけですね。 最終目標は、以下のようにして階乗を計算する関数を定義することができるようになることです。 fact = y[lambda{|h| lambda{|n| if n < 2 1 else n * h[n - 1] end } ] ) puts fact[10] ここで出てきたyが、Y Combinatorと呼ばれるものです。 見やすさの為に、factという名前をつけましたが、関数を定義するところではfact
Rubyのある風景 - Y+Combinator+2
以前取り上げたY Combinatorですが、何故"Y"なのかと思って調べてみたところ、どうやら"To Mock a Mockkingbird" がもとになっているようです。 この本では色々な鳥の名前を各ラムダ式に割り当てて、組み合わせ理論(Combinatory Logic)を解説しています。 ちなみにYは"Why Bird (aka Sage Bird)"だそうで。 さて、組み合わせ理論の有名な話として、 K = λxy.x S = λxyz.xz(yz) の二つを用いることで、チューリングマシンと等価な計算能力が得られるということが知られています(ということは、この二つさえあれば、今一般に使われているプログラムは全て記述できるわけですね)。 例えば、恒等写像I(λx.x)は SKK = (λxyz.xz(yz))(λxy.x)(λxy.x) = (λyz.(λxy.x)z(yz))(
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Fei Ling's website
