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