不動点演算子

昨日のYコンビネータを考えてるときに気がついたことをメモ。
準備として、不動点演算子とは、任意の関数fに対して

Y(f) == f(Y(f))

を満たすYのこと*1。
昨日の最後のコード

y =
lambda{|q|
  p = lambda{|f|
    lambda{|n|
      f[f][n]
    }
  }
  g = lambda{|u|
    lambda{|v|
      q[u[u]][v]
    }
  }
  p[g]
}

h =
lambda{|slf|
  lambda{|m|
    if m == 0
      1
    else
      m * slf[m-1]
    end
  }
}

fact = y[h]
p fact[10]

で、hの型を考えてみた。型付けの表現はHaskell風の擬似コードで。

h :: (Int -> Int) -> Int -> Int

カリー化されてるのでhは、『(整数→整数)な関数を受け取って、(整数→整数)な関数を返す関数』となる。
hの実装を見ると、

h :: (Int -> Int) -> Int -> Int
     ^^^^^^^^^^^^    ^^^^^^^^^^
      factorial       factorial

になっている。もう少し詳しく言うと、「階乗関数を入れると階乗関数を返す」関数になっている。そのほかの関数を入れた場合はその限りではない。
このhから階乗関数を出してくるということは、

h(fact) = fact

となるfactを求めることで、つまりhの不動点を求めることになっている。
それをやるのが、Yコンビネータのyとなる。

これで以前からよくわからなかった

• Yコンビネータが不動点演算子であること
• 不動点演算子が無名再帰関数を作り出すこと

がつながった。
まあ、yのあんな感じの実装で不動点を生成するというのは、パッと見で全然見当つかないし、ふしぎだなぁという感覚は残っているけど。
あと、Haskellで

y f = f (y f)

と定義したらちゃんと動くんだろうか。展開される様が想像できない。

y f = f (y f)

fact' :: (Integer -> Integer) -> Integer -> Integer
fact' _ 0 = 1
fact' f n = n * f (n - 1)

fact = y fact'

main = putStrLn (show (fact 10))

おお！動いた。へー。

*1:たぶん