不動点コンビネータを使うと、どうして無名関数で再帰ができるのかを考えてみる。
名前を取り去る
以下の階乗を計算する関数 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
