3.hs

{-# LANGUAGE Rank2Types #-}

newtype Church = Church (forall a. (a -> a) -> (a -> a))

zero' = Church (\f x -> x)
one' = Church (\f x -> f x)
two' = Church (\f x -> f $ f x)
three' = Church (\f x -> f $ f $ f x)
succ' (Church n) = Church (\f -> f . n f)
add' (Church a) (Church b) = Church (\f x -> b f $ a f x)
sub' a b = fromInteger $ max 0 (fromChurch a - fromChurch b)
mult' (Church a) (Church b) = Church (a . b)

fromChurch (Church n) = n (+ 1) 0

instance Eq Church where
    (==) a b = (fromChurch a) == (fromChurch b)

instance Ord Church where
    (<=) a b = (fromChurch a) <= (fromChurch b)

instance Show Church where
    show n = show (fromChurch n)

instance Num Church where
    (+) = add'
    (-) = sub'
    (*) = mult'
    abs n = n
    signum n = if (fromChurch n) == 0 then zero' else one'
    fromInteger i = iterate succ' zero' !! (fromIntegral i)