あどけない話

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

Yコンビネータのまとめ

不動点

関数 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 36

この動作原理を考える。まず、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))

リンク集

不動点コンビネータの内、Lx(Lx) (BML や SLL のこと?) だけを Y コンビネータと呼ぶそうだ。不動点コンビネータの別名が Y コンビネータだと勘違いしていた。以下を読むときは、訂正しながら読んでほしい。