Haskell で Y コンビネータ

Haskell では、Y コンビネータが作れないと誤解している人がいるので、できることを示すと同時に、これまで学んだことをまとめてみます。

遅延評価を活かした Y コンビネータ

関数名を用いた再帰を使ってよいなら、Haskell では遅延評価のおかげで、Y コンビネータを定義である Y x = x (Y x) の通りに書けます。

y :: (a -> a) -> a
y x = x (y x)

Y コンビネータ用の階乗を定義してみましょう。

fact :: Num a => (a -> a) -> a -> a
fact = \f n -> if n == 0 then 1 else n * f (n-1)

以下のように動きます。

y fact 4
→ 24

でも、この階乗は Haskell っぽくないので、入り口で分岐するように書き直してみます。

fact :: Num a => (a -> a) -> a -> a
fact _ 0 = 1
fact f n = n * f (n-1)

fact という名前では、再帰してませんよ。これも期待通りに動きます。

y fact 4
→ 24

型推論をごまかす Y コンビネータ

定義通りの実装では、Y コンビネータ自身は再帰を使って定義しました。ラムダ計算がチューリング完全であることを示すのが目的であれば、この定義はインチキです。ラムダ計算には、名前を使った再帰がないからです。名前を使った再帰がない条件の下に、Y コンビネータを作らないといけません。

よく Scheme とかで実装された Y コンビネータは、ゴチャゴチャしていて分かりにくいと思うので、分割して実装してみましょう。

import Unsafe.Coerce

s :: (a -> b -> c) -> (a -> b) -> a -> c
s x y z = x z (y z)

l :: (a -> b) -> (c -> a) -> b
l x y = x (y (unsafeCoerce y))

y :: (a -> a) -> a
y = s l l

Y コンビネータの実装方法はたくさんあります。これは SLL と表現できる Y コンビネータです。どの関数も再帰を使っていないことに注意して下さい。

L の定義は、本当は L x y = x (y y) です。(y y)の部分が自己言及になって、GHC ではこの部分の型をうまく処理できません。そこで、unsafeCoerce で型推論をごまかしています。

実際に動くことを確かめておきましょう。

y fact 4
→ 24

上記の定義では、いきなり L を使いましたが、もっと根源的な S と K のみから出発して、Y にたどり着くこともできます。

s :: (a -> b -> c) -> (a -> b) -> a -> c
s x y z = x z (y z)

k :: a -> b -> a
k x y = x  -- aka const

i :: a -> a
i = s k k -- aka id

c :: (a -> b -> c) -> b -> a -> c
c = s (b b s) (k k) -- aka flip

b :: (b -> c) -> (a -> b) -> a -> c
b = s (k s) k  -- aka (.)

m :: (a -> b) -> b
m = s i (unsafeCoerce i)

l :: (a -> b) -> (c -> a) -> b
l = c b m

y :: (a -> a) -> a
y = s l l

(ものまね鳥) M が自己言及するので、unsafeCoerce で型をごまかしています。(ちなみに、y = b m l でも OK)

型推論をごまかさない Y コンビネータ

型推論をごまかさなくても、newtype を使って型を定義し、inline 化をプラグマで止めれば、Y コンビネータが実装できます。上記のコードの m 以降を以下で置き換えて下さい。

newtype I a = I (I a -> a)

unI :: I a -> I a -> a
unI (I x) = x
{-# NOINLINE unI #-}

m :: I a -> a
m = s unI i

l :: (a -> b) -> I a -> b
l = c b m

y :: (a -> a) -> a
y = s l (b I l) -- s l (I . l)

ちゃんと動きますね。

y fact 4
→ 24

この方法は、Oleg さんに教えていただきました。ありがとうございます。

おまけ

Sxyz = xz(yz)     -- <*>
Kxy = x           -- const
Ix = x            -- id,   I = SKK
Bxyz = x(yz)      -- (.),  B = S(KS)K
Cxyz = xzy        -- flip, C = S(BBS)(KK) 
Txy = yx          --       T = CI
Wxy = xyy         --       W = SS(KI) = ST
Mx = xx           --       M = SII = STT = WI = WT
Lxy = x(yy)       --       L = CBM = BWB = QM
Qxyz = y(xz)      --       Q = CB
Oxy = y(xy)       --       O = SI
Uxy = y(xxy)      --       U = LO
Yx = x(Yx)        --       Y = SLL = BML = UU

• Combinator Birds