Yコンビネータによる無名再帰をRubyで理解する
アンダースタンディング コンピュテーション180ページでは、Yコンビネータ(Zコンビネータ)によって無名再帰を実装している。
が、詳しい説明が省かれているので、Wikipediaの不動点コンビネータの例をRubyで書いて理解してみる。
まず普通に再帰を使って、階乗を実装する。
Fac = -> x { if x.zero? 1 else x * Fac[x-1] end }
このコードは次のように書き直しても同じである。
Fac = -> x { U[Fac, x] } U = -> (f, x) { if x.zero? 1 else x * f[x-1] end }
さらにUをカリー化して、次のようにしても同じ。
Fac = -> x { V[Fac][x] } V = -> f { -> x { if x.zero? 1 else x * f[x-1] end } }
ここで Fac
に注目すると、引数を省けば、次のような構造になっている。
Fac = V[Fac]
実際には引数の評価を遅延しないと動作しないが、これはV
に対する不動点の定義そのものである。
よって不動点コンビネータでV
の不動点を求めれば、それがFac
と同じものになる。
f2 = Z[V]
まとめて書けば次の通り。
Fac = Z[-> f { -> x { if x.zero? 1 else x * f[x-1] end } }]