あどけない話

インターネットに関する技術的な話など

不動点の話

不動点コンビネータを使うと、どうして無名関数で再帰ができるのかを考えてみる。

名前を取り去る

以下の階乗を計算する関数 fact を考える。

fact 0 = 1
fact n = n * fact (n - 1)

これは、以下のように一つの式に変形できる。

fact n = if n == 0 then 1 else n * fact (n - 1)

さらに、ラムダ式に変形できる。

fact = \n -> if n == 0 then 1 else n * fact (n - 1)

ここで、fact という名前は使えないので、関数を引数に取るように変更してみる。

fact = (\g n -> if n == 0 then 1 else n * g (n - 1)) fact  (※1)

不動点登場

※1 の無名関数を h で表すとする。

fact = h fact  (※2)

ここで、x が f の不動点を示す式と比べてみる。

f x = x

二つの式を比べると、fact が h の不動点となっていることが分かる。不動点再帰できる理由は、これがすべてだが、もう少し続ける。

不動点コンビネータ

今、h の不動点 fact を h から求めたい。その仕事をする関数を fix と呼ぶとすると、

fact = fix h  (※3)

※3を※2に代入すると、

fix h = h (fix h)

となる。

動かしてみる

fact 3 = fix h 3
       = h (fix h) 3
       = if 3 == 0 then 1 else 3 * (fix h) 2
       = 3 * (fix h) 2
       = 3 * h (fix h) 2
       = 3 * (if 2 == 0 then 1 else 2 * (fix h) 1)
       = 3 * 2 * (fix h) 1
       = 3 * 2 * h (fix h) 1
       = 3 * 2 * (if 1 == 0 then 1 else 1 * (fix h) 0)
       = 3 * 2 * 1 * (fix h) 0
       = 3 * 2 * 1 * h (fix h) 0
       = 3 * 2 * 1 * (if 0 == 0 then 1 else 0 * (fix h) 0)
       -- 遅延評価なので else 節は計算されない
       = 3 * 2 * 1 * 1
       = 6