Church encoding

gistfile1.hs

-- numbers
 
zero _ = id
one f  = f
two f  = f . f
 
-- numeric operators
 
succ n f   = f . (n f)
plus m n f = (n f) . (m f)
mult m n f = m (n f)
exp  m n f = (n m) f

-- boolean

true x y  = x -- \x -> \y -> x
false x y = y -- \x -> \y -> y

if' cond x y = cond x y -- id
or x y = x true y    -- if' x true (if' y true false)
and x y = x y false  -- if' x (if' y true false) false
not x = x false true -- if' x false true

-- predicates

isZero f = f (\_ -> false) true

-- pair

pair x y = \f -> f x y

left  p = p (\x y -> x)  
right p = p (\x y -> y)  
 
-- as int
 
int f = f (+1) 0

-- as boolean

bool f = f True False