Yコンビネータによる再帰 のバックアップ(No.1)

更新


公開メモ

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 factorial(n-1) * n

alert factorial(4) 
# displays 4! == 24

1の階乗は1。

nの階乗はn-1の階乗にnを書けた物。

という素直な実装です。

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 reccurse(n-1) * n

alert factorial_y(4) 
# displays 4! == 24

factorial_y を精査する

factorial_y は reccurse という関数を受け取って、 「引数 n を取る関数」を返す形に直されています。

そして、再帰呼び出しをする

      return factorial(n-1) * n

が、仮引数で渡される reccurse に置き換えられて

      return reccurse(n-1) * n

となっています。

あたかも reccurse の呼び出しが自分自身を再帰呼び出しするような関数を 外部から与えられると期待しているようですね。

y_combi を精査する

1行目から分かるように、y_combi は func を渡すと何かを返す関数です。

func には factorial_y のような関数が与えられます。

何が返されるか、は、かなり複雑なのですが、y_combi の中身は

LANG:coffeescript(linenumber)
y_combi = (func)->
  return ((p)->
    ...

  )((p)->
    ...

  )

という形になっていますので、2行目の (p)-> から始まる関数に、 5行目の (p)-> から始まる関数を引数として与えた結果を返すと読めます。

2つの ... の内容は等しいので、2行目の (p)-> から始まる関数と、 5行目の (p)-> から始まる関数の内容は等しいです。

ですので、こう書き直しても同じ動作をします。

LANG:coffeescript(linenumber)
y_combi = (func)->
  core = (core)-> (n)-> func(core(core))(n)
  return core(core)

関数型変数の core と、λ式の仮引数の core の名前をわざと同じにしたせいで、 スコープがややこしいかもしれませんが、実際には引数にも core 自身が渡されるため、 結果的に core と書かれた部分にはすべて等しい値が入ります。

そして、factorial_y の y_combi に続く (reccurse)-> 以下が y_combi の func に対応することを考えると、 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) を返します。

という具合で、確かに正しく求まりそうなことがようやく理解できました。


Counter: 4308 (from 2010/06/03), today: 4, yesterday: 0