404 Blog Not Found:Y combinator is forbidden in Haskell!?
な、なんかおいらはな、なっとくいかねーぞー!

に対して、正三郎さんから

Y Combinator(Yコンビネータ)がHaskellで書けない!?: ホットコーナーの舞台裏
でも、HaskellでY Combinator(Yコンビネータ)は、書けるようね。たとえば、これ。

せっかく実演できる環境があるのでやってみました。

LLEvalで。

newtype Mu a = Roll (Mu a -> (a -> a))
unroll (Roll x) = x

-- y4h :: (a -> a) -> a -> a
y4h = \f -> (\x z -> f ((unroll x) x z))
        (Roll (\x z -> f ((unroll x) x z)))

-- _fact :: (Int -> Int) -> Int -> Int
_fact f x = if x <= 0
               then 1
               else x * (f (x-1))

-- fact :: Int -> Int
fact = y4h  _fact undefined

main = print $ fact 10

LLEvalではGHCではなくhugsなので、[Haskell] How to define Y combinator in Haskellがそのまま動きます。ここでは型推論がうまく行っていることを示すため、型宣言はコメントアウトしています。

でもなんで

fact = y4h  _fact

も

fact n = y4h _fact n

も型を推論できないんだろう?undefinedなんてあったのですねえ。

Dan the Blogger Combinator