public
Created

Church Number

  • Download Gist
Church.hs
Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
module Church where
 
import Prelude ((.), ($), id, fst, undefined, length)
 
zero f = id
inc n f = f . n f
 
one f = f
two f = f . f
three f = f . f . f
 
succ n f = f . n f
plus m n f = m f . n f
mult m n = (n . m) -- mult m n f = plus m (plus m ... ) f
-- = m f . m f . ...
-- = (m f)^n
-- = n (m f)
-- = (n . m) f
 
exp m n = n m -- exp m n = (mult m (mult m ... ))
-- = m . m . ... = n m
 
-- next (x, y) = (y, succ y)
-- pred n = fst $ n next (undefined, zero)
 
cons x y = \m -> m x y
car z = z (\p q -> p)
cdr z = z (\p q -> q)
 
next z = cons (cdr z) (succ (cdr z))
pred n = car $ n next (cons undefined zero)
 
sub m n = n pred m -- 类型错误啊,坑爹!!!
 
true = \a b -> a
false = \a b -> b
 
isZero n a b = n (\_ -> b) a
 
and x y a b = x (y a b) b
or x y a b = x a (y a b)
not x a b = x b a
xor x y a b = x (y b a) (y a b)
 
ifElse m a b = m a b
 
showChurch n = length $ n (undefined:) []
showChurchBool n = length $ n [undefined] []

sub m n = n pred m有问题。

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.