指数函数Haskell

Question

如何利用Haskell获得教堂数字中的幂函数？

我正在尝试应用这个规则，那就是λxy.yx，但是有些东西不能正常工作。

exponentiation :: (Num a) => Func a
exponentiation x y = y x

Answer 1

教会数字算术往往涉及相当奇怪的类型，所以它在哈斯克尔不太优雅，在一种非类型化的语言。原则上，教会数字是一个接受任何https://en.wikipedia.org/wiki/Endomorphism并在同一类型上给出另一个自同态的函数，即

five :: (a -> a) -> a -> a

它适用于任何类型的a，也就是说，它实际上意味着

{-# LANGUAGE ExplicitForall, UnicodeSyntax #-}
five :: ∀ a . (a -> a) -> a -> a

当你用这样的数字做有趣的算术时的诀窍是，计算的各个组成部分实际上可能是处理不同类型的自同态，包括本身是高阶函数的自同态。要追踪这一切会变得相当棘手。

因此，在Haskell中玩Church算术最不痛苦的方法是将所有多态性封装为自然数的单一类型(其实现恰好是教堂编码)：

{-# LANGUAGE RankNTypes, UnicodeSyntax #-}
newtype Nat = Nat {getChurchNum :: ∀ a . (a -> a) -> a -> a}

然后，您可以为所有基本操作提供清晰的类型签名，只需要在Nat包装器中放置与数字相对应的术语，以隐藏多态性：

zero :: Nat
zero = Nat (\f x -> x)

suc :: Nat -> Nat
suc = \(Nat n) -> Nat (\f x -> n f (f x))

...or，我更喜欢写它，

instance Enum Nat where
  succ (Nat n) = Nat (\f -> n f . f)

instance Num Nat where
  fromInteger 0 = Nat (const id)
  fromInteger n = succ . fromInteger $ n-1
  Nat a + Nat b = Nat (\f -> a f . b f)
  Nat a * Nat b = Nat (a . b)

instance Show Nat where
  show (Nat n) = show (n (+1) 0 :: Int)

快速测试：

GHCi> [0, 1, 2, 4, 8, 3+4, 3*4 :: Nat]
[0,1,2,4,8,7,12]

现在，使用这些类型，您还可以直接实现指数：

pow :: Nat -> Nat -> Nat
pow (Nat n) (Nat m) = Nat (m n)

它如预期的那样工作：

GHCi> [pow a b :: Nat | a<-[0,1,2,3], b<-[0,1,2,3]]
[1,0,0,0,1,1,1,1,1,2,4,8,1,3,9,27]

Answer 2

下面是另一个使用WinHugs的示例

type Church a = (a -> a) -> a -> a

zero :: Church a
zero = \s z -> z

one :: Church a
one = \s z -> s z

two :: Church a
two = \s z -> s (s z)

three :: Church a
three = \s z -> s (s (s z))

four :: Church a
four = \s z -> s (s (s (s z)))

succ :: Church a -> Church a
succ n f = f . n f

add :: Church a -> Church a -> Church a
add x y = \s z -> x s (y s z)

mult :: Church a -> Church a -> Church a
mult x y = x.y

exp :: Church a -> (Church a -> Church a) -> Church a
exp x y = y x

测试操作add、mult和exp (使用s=(+1)和z=0)：

Main> add two three (+1) 0
5
Main> mult four three (+1) 0
12
Main> exp two three (+1) 0
8

测试操作add、mult和exp (使用s=('|':)和z="")：

Main> add two three ('|':) ""
"|||||" --5 sticks
Main> mult four three ('|':) ""
"||||||||||||" --12 sticks
Main> exp two three ('|':) ""
"||||||||" --8 sticks

或exp four two (4^2 = 16)，它写成：

Main> two four (+1) 0
16

很好用！