gistfile1.txt

newtype ChurchNat = ChurchNat { foldNat :: forall r. r -> (r -> r) -> r }

zero :: ChurchNat
zero = ChurchNat (\z _ -> z)

suc :: ChurchNat -> ChurchNat
suc n = ChurchNat (\z s -> s (foldNat n z s))

fromInt :: Int -> ChurchNat
fromInt 0 = zero
fromInt n = suc (fromInt (n-1))

toInt :: ChurchNat -> Int
toInt n = foldNat n 0 (\r -> 1+r)

plus :: ChurchNat -> ChurchNat -> ChurchNat
plus x y = foldNat x y (\r -> suc r)

fib :: ChurchNat -> ChurchNat
fib n = fst (foldNat n (suc zero, suc zero) (\(a,b) -> (b,plus a b)))


main :: IO ()
main = print [ toInt (fib (fromInt n)) | n <- [0..5] ]