指数函数Haskell

Question

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

我正在尝试应用规则,即λxy.yx,但有些东西不能正常工作.

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

Answer 1

教会数字算术往往涉及相当奇怪的类型,因此它在Haskell中并不像在非类型语言中那样优雅.原则上,教会数字是一种功能,它接受任何内同态并在同一类型上给出另一种内同态,即

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

适用于任何类型a,即它真正意味着

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

当你用这样的数字做有趣的算术时,技巧是计算的各个组成部分实际上可能正在处理不同类型的内同态,包括本身就是高阶函数的内同态.跟踪这一切变得非常棘手.

因此,在Haskell中使用Church算法玩弄最不痛苦的方法是将所有多态性包装成自然数的单个类型(其实现恰好是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))

......或者,因为我更喜欢写它,

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]