不動点
関数 f :: a -> a に対して、f x == x となる x を「関数 f の不動点」という。
もし、関数 f を入力として取り、関数 f の不動点を返す関数 Y があるとすれば、関数 f の不動点を Y f と表現できる。
ここで、Y の型を調べる。引数 f の型は a -> a、Y は不動点を返すから返り値の型は a。よって、Y :: (a -> a) -> a となる。
不動点 x = Y f を f x == x に代入すると、Y f == f (Y f) となる。これを Haskell で実装すると、関数名に大文字が使えるとして、以下のようになる。
Y x = x (Y x)
再帰の例
再帰するときに自分の関数名を使わない階乗のプログラム fact を以下のように定義する。
fact :: Num a => (a -> a) -> a -> a fact = \f n -> if n == 0 then 1 else n * f (n-1)
Y に fact を与えて、実際に動かしてみる。
Y fact 3 → 6
この動作原理を考える。まず、Y の性質から、以下のような関係があることを知っている。
Y fact = fact (Y fact)
この関係を使って Y fact 3 を簡約してみる。
Y fact 3 = fact (Y fact) 3 = if 3 == 0 then 1 else 3 * (Y fact) 2 = 3 * (Y fact) 2 = 3 * fact (Y fact) 2 = 3 * (if 2 == 0 then 1 else 2 * (Y fact) 1) = 3 * 2 * (Y fact) 1 = 3 * 2 * fact (Y fact) 1 = 3 * 2 * (if 1 == 0 then 1 else 1 * (Y fact) 0) = 3 * 2 * 1 * (Y fact) 0 = 3 * 2 * 1 * fact (Y fact) 0 = 3 * 2 * 1 * (if 0 == 0 then 1 else 0 * (Y fact) 0) -- 遅延評価なので else 節は計算されない = 3 * 2 * 1 * 1 = 6
Y コンビネータの導出
不動点コンビネータの一例である Y コンビネータを導く。まず、以下のような L コンビネータを見つけられたとする。
Lxy = x(yy)
すると、Lx(Lx) は x の不動点である。なぜなら、L の定義において y は任意であるから、y = Lx と置くと：
Lx(Lx) = x(Lx(Lx))
左右をひっくり返せば：
x(Lx(Lx)) = Lx(Lx)
よって、Lx(Lx) は x の不動点である。次に、以下のような M コンビネータを発見できたとする。
Mx = xx
M の x は任意であるので Lx で置き換えると：
M(Lx) = Lx(Lx)
最後に、B コンビネータが発見できたとする。(Haskell 使いなら、誰でも (.) は発見できる！)
Bxyz = x(yz)
x を M、y を L、z を x とすれば：
BMLx = M(Lx) = Lx(Lx) = 不動点
よって、BML が不動点コンビネータに他ならない。これを Y コンビネータと呼ぶ。
Yx = BMLx
もっと簡単に：
Y = BML
実際に簡約してみる：
Yx = BMLx = M(Lx) = Lx(Lx) = x(Lx(Lx)) = x(Yx)
λ式で書く
Y をλ式で書くとこうなる。
L x y = x (y y) L x = \y -> x (y y) Yx = L x (L x) = (\y -> x (y y)) (\y -> x (y y)) M z = z z M = \z -> z z Y x = M (L x) = (\z -> z z) (\y -> x (y y))
