Typing the Y combinator in Haskell.

Y.hs

{- Typing the Y combinator in Haskell.
 - $ runghc Y.hs
   720
   Succ (Succ (Succ (Succ (Succ (Succ Zero)))))
 -}

newtype Fix a = Fix { unfix :: Fix a -> a }

fix :: (Fix a -> a) -> Fix a
fix x = Fix x

y :: (a -> a) -> a
y f = g (fix g)
    where g x = f (unfix x $ x)

-- The factorial function.
fact :: (Integer -> Integer) -> Integer -> Integer
fact _ 0 = 1
fact self n = n * self (n - 1)

-- A representation of natural numbers.
data Nat = Zero | Succ Nat
   deriving Show

int2nat :: (Integer -> Nat) -> Integer -> Nat
int2nat _ 0 = Zero
int2nat self n = Succ (self (n - 1))

main :: IO ()
main = let factResult = y fact 6
           convResult = y int2nat 6
       in do putStrLn (show factResult)
             putStrLn (show convResult)