ChurchNumbers.hs

{-# LANGUAGE RankNTypes #-}

import Prelude hiding (succ)

newtype CNumber = Nr (forall t. (t -> t) -> t -> t)

zero :: CNumber
zero = Nr (\ f x -> x )
one = Nr (\ f x -> f x )
two = Nr (\ f x -> f (f x) )

eval :: CNumber -> Int
eval (Nr n) = n (+1) 0

succ :: CNumber -> CNumber
succ (Nr a) = Nr (\ f x -> f (a f x) )

add :: CNumber -> CNumber -> CNumber
-- add (Nr a) (Nr b) = Nr (\ f x -> a f (b f x))
add (Nr a) (Nr b) = a succ (Nr b)
-- add (Nr a) = a succ

mult :: CNumber -> CNumber -> CNumber
mult (Nr a) (Nr b) = a (add (Nr b)) zero
-- mult (Nr a) b = a (add b) zero

pow :: CNumber -> CNumber -> CNumber
pow (Nr a) (Nr b) = b (mult (Nr a)) one
-- pow a (Nr b) = b (mult a) one