Yコンビネータによる再帰
Yコンビネータによる再帰†
http://qiita.com/mrpepper/items/6a538ef0b2d11fc311ac
こちらの記事を読んで、Yコンビネータによる再帰の方法を知りました。
が、一見しただけだとどんな仕組みで動作しているのかが分からなかったので、勉強してみました。
ここではYコンビネータの数学的な話などは全部置いておいて、 コードとしてなぜこれが動くのか、を理解したいと思います。
言語としては Coffee Script を使っています。
http://coffeescript.org/ こちらの一番上で TRY COFFEESCRIPT にコードを貼って、右上の run で走らせることができます。
まずは通常の再帰処理コード†
恐らくもっとも有名な、階乗計算のコードはこんな感じ。
LANG:coffeescript
factorial = (n)->
if n == 1
return 1
else
return n * factorial(n-1)
alert factorial(4)
# displays 4! == 24
１の階乗は１。
ｎの階乗はｎ－１の階乗にｎを掛けた物。
という素直な実装です。
Yコンビネータを使ったコード†
上記サイトのコードを少し変更して、以下のような物を試してみたところ、 驚くべきことに(!) 正しく 24 が表示されました。
LANG:coffeescript(linenumber)
y_combi = (func)->
return ((p)->
return (n)->
return func(p(p))(n)
)((p)->
return (n)->
return func(p(p))(n)
)
factorial_y = y_combi (reccurse)->
return (n)->
if n == 1
return 1
else
return n * reccurse(n-1)
alert factorial_y(4)
# displays 4! == 24
factorial_y を精査する†
factorial_y は reccurse という関数を受け取って、 「引数 n を取る関数」を返す関数に y_combi を適用した形に直されています。
そして、再帰呼び出しをする
LANG:coffeescript
return n * factorial(n-1)
が、仮引数で渡される reccurse に置き換えられて
LANG:coffeescript
return n * reccurse(n-1)
となっています。
reccurse を呼び出すことで自分自身を再帰呼び出しできるような 引数が外部から与えられると期待しているようですね。
y_combi を精査する†
１行目から分かるように、y_combi は func を渡すと何かを返す関数です。
func には factorial_y の (reccurse)-> 以下のような関数が与えられます。
y_combi から何が返されるか、を読むのは、なかなか骨が折れますね。
y_combi の中身は
LANG:coffeescript(linenumber)
y_combi = (func)->
return ((p)->
...
)((p)->
...
)
という形になっていますので、２行目の (p)-> から始まる関数に、 ５行目の (p)-> から始まる関数を引数として与えた結果を返すと読めます。
２つの ... の内容は等しいので、２行目の (p)-> から始まる関数と、 ５行目の (p)-> から始まる関数の内容は等しいです。
ですので、こう書き直しても同じ動作をします。
LANG:coffeescript y_combi = (func)-> core = (core)-> (n)-> func(core(core))(n) return core(core)
関数型変数の core と、λ式の仮引数の core の名前をわざと同じにしたせいで、 スコープがややこしいかもしれませんが、実際には引数にも core 自身が渡されるため、 結果的に core と書かれた部分にはすべて等しい値が入ります。
func に core(core) を与えて呼び出していますので、 factorial_y の中の reccurse には core(core) が入ることになります。
core(core) は (n)-> func(core(core))(n) を返すので、
func(core(core))(n) の中で呼ばれる reccurse(n-1) は core(core)(n-1) のことで、 これは func(core(core))(n-1) を返します。
func(core(core))(n-1) の中で呼ばれる reccurse(n-2) は core(core)(n-2) のことで、 これは func(core(core))(n-2) を返します。
func(core(core))(n-2) の中で呼ばれる reccurse(n-3) は core(core)(n-3) のことで、 これは func(core(core))(n-3) を返します。
という具合で、確かに正しく求まりそうなことがようやく理解できました。
実行効率†
これ、確かに動きそうですが、実行効率はどうでしょう。
factorial が n 重の関数再帰呼び出しで計算可能です。
Yコンビネータを使った方では、func, core が適切に設定されている前提では
LANG:coffeescript factorial_y = (n)-> func(core(core))(n)
ですので、見た目の複雑さに反してこちらも n 回の再帰で済みますが、 同時に core(core) の計算を n 回行っている分だけ余計な計算が必要です。
思ったほどは効率に影響がないので、末尾再帰の最適化などが実装されると、 ばりばり使っても問題ないのかもしれません？
Y コンビネータの代わりにこれじゃダメなのかしら？†
LANG:coffeescript y_combi = (func) -> caller= (n) -> func(caller)(n)
以下のようにすれば任意個数の引数にも対応できます。
LANG:coffeescript y_combi = (func) -> caller= (args...) -> func(caller)(args...)
正しく動きそうなことを以下で確認できます。
http://jsbin.com/hudaziyusa/edit?js,console
下記にわかりやすい記事を発見しました。
http://d.hatena.ne.jp/amachang/20080124/1201199469
たぶん、わざわざ Y コンビネータを使うのは理論的な意味合いしかないという理解で合っていそうです。
「工夫次第では再起処理まですべてラムダ形式で書けるよね、すごいよね」ということだと思っていればよいような。
一方で、
LANG:coffeescript y_combi = (func) -> caller= (args...) -> func(caller)(args...)
こういう実装でＹコンビネータと同じ意味合いの処理を書き、それを使って非同期処理を書くことにはそれなりの意味がありそう？
なのかなあ？？？