一些带有教堂数字的操作的类型签名声明

Question

我试图在 Haskell 中实现教堂数字。这是我的代码：

-- Church numerals in Haskell.
type Numeral a = (a -> a) -> (a -> a)

churchSucc :: Numeral a -> Numeral a
churchSucc n f = \x -> f (n f x)

-- Operations with Church numerals.
sum :: Numeral a -> Numeral a -> Numeral a
sum m n = m . churchSucc n

mult :: Numeral a -> Numeral a -> Numeral a
mult n m = n . m

-- Here comes the first problem
-- exp :: Numeral a -> Numeral a -> Numeral a
exp n m = m n

-- Convenience function to "numerify" a Church numeral.
add1 :: Integer -> Integer
add1 = (1 +)

numerify :: Numeral Integer -> Integer
numerify n = n add1 0

-- Here comes the second problem
toNumeral :: Integer -> Numeral Integer
toNumeral 0 = zero
toNumeral (x + 1) = churchSucc (toNumeral x)

我的问题来自求幂。如果我声明 toNumeral 和 exp 的类型签名，则代码无法编译。但是，如果我评论类型签名声明，一切正常。 toNumeral 和 exp 的正确声明是什么？

Answer 1

exp 不能按照您的方式编写的原因是它涉及将 Numeral 作为参数传递给 Numeral。这需要有一个Numeral (a -> a)，但你只有一个Numeral a。你可以写成

exp :: Numeral a -> Numeral (a -> a) -> Numeral a
exp n m = m n

我看不出 toNumeral 有什么问题，除了不应该使用像 x + 1 这样的模式。

toNumeral :: Integer -> Numeral a -- No need to restrict it to Integer
toNumeral 0 = \f v -> v
toNumeral x
  | x > 0 = churchSucc $ toNumeral $ x - 1
  | otherwise = error "negative argument"

另外，你的 sum 被窃听了，因为 m . churchSucc n 是 m * (n + 1)，所以它应该是：

sum :: Numeral a -> Numeral a -> Numeral a
sum m n f x = m f $ n f x -- Repeat f, n times on x, and then m more times.

但是，教堂数字是适用于所有类型的函数。也就是说，Numeral String 不应该与 Numeral Integer 不同，因为 Numeral 不应该关心它正在处理什么类型。这是一个通用量化：Numeral是一个函数，对于所有类型a，(a -> a) -> (a -> a)，写成，用RankNTypes , 作为 type Numeral = forall a. (a -> a) -> (a -> a).

这是有道理的：教堂数字是由其函数参数重复的次数来定义的。 \f v -> v 调用 f 0 次，所以它是 0，\f v -> f v 是 1，等等。强制 Numeral 为所有 a 工作确保它可以只有这样做。但是，允许 Numeral 关心 f 和 v 的类型会移除限制，并允许您编写 (\f v -> "nope") :: Numeral String，即使这显然不是 [=16] =].

我会这样写

{-# LANGUAGE RankNTypes #-}

type Numeral = forall a. (a -> a) -> (a -> a)

_0 :: Numeral
_0 _ x = x
-- The numerals can be defined inductively, with base case 0 and inductive step churchSucc
-- Therefore, it helps to have a _0 constant lying around

churchSucc :: Numeral -> Numeral
churchSucc n f x = f (n f x) -- Cleaner without lambdas everywhere

sum :: Numeral -> Numeral -> Numeral
sum m n f x = m f $ n f x

mult :: Numeral -> Numeral -> Numeral
mult n m = n . m

exp :: Numeral -> Numeral -> Numeral
exp n m = m n

numerify :: Numeral -> Integer
numerify n = n (1 +) 0

toNumeral :: Integer -> Numeral
toNumeral 0 = _0
toNumeral x
  | x > 0 = churchSucc $ toNumeral $ x - 1
  | otherwise = error "negative argument"

相反，它看起来更干净，而且比原来的运行更不容易遇到障碍。

演示：

main = do out "5:" _5
          out "2:" _2
          out "0:" _0
          out "5^0:" $ exp _5 _0
          out "5 + 2:" $ sum _5 _2
          out "5 * 2:" $ mult _5 _2
          out "5^2:" $ exp _5 _2
          out "2^5:" $ exp _2 _5
          out "(0^2)^5:" $ exp (exp _0 _2) _5
       where _2 = toNumeral 2
             _5 = toNumeral 5
             out :: String -> Numeral -> IO () -- Needed to coax the inferencer
             out str n = putStrLn $ str ++ "\t" ++ (show $ numerify n)

一些带有教堂数字的操作的类型签名声明

Type signature declaration of some operations with Church numerals

haskell

church-encoding