Haskell 中的教堂数字

Question

我正在尝试使用以下定义在 haskell 中打印教堂数字：

0 := λfx.x
1 := λfx.f x

Haskell 代码：

c0 = \f x -> x
c1 = \f x -> f x

当我在 haskell 控制台中输入它时，我收到一个错误，表示

    test> c1

    <interactive>:1:0:
    No instance for (Show ((t -> t1) -> t -> t1))
      arising from a use of `print' at <interactive>:1:0-1
    Possible fix:
      add an instance declaration for (Show ((t -> t1) -> t -> t1))
    In a stmt of an interactive GHCi command: print it

我无法准确弄清楚错误所说的内容。

谢谢你！

Answer 1

这里的问题是，默认情况下，不可能在 Haskell 中打印值。打印内容的默认方法（由 print 函数和 GHCi REPL 等使用）是 show 函数，由类型类 定义显示。

那么，您收到的错误是通知您计算的表达式的类型没有定义 Show 实例。模数一些措辞，这就是错误消息的全部内容：

No instance for (Show ((t -> t1) -> t -> t1))

类型 ((t -> t1) -> t -> t1) 是为您评估的表达式推断出的类型。这是 Church 数字 1 的有效类型，尽管 Church 数字的“正确”类型实际上应该是 (a -> a) -> 。一个->一个。

  arising from a use of `print' at <interactive>:1:0-1

它隐式使用 print 函数来显示值。通常这会告诉您在程序中的哪个位置发现了错误，但在本例中它显示 :1:0-1 因为错误是由 REPL 中的表达式引起的。

Possible fix:
  add an instance declaration for (Show ((t -> t1) -> t -> t1))

这只是建议您可以通过定义所需的实例来修复错误。

---

现在，您可能想要实际打印您的教堂数字，而不仅仅是知道为什么不能。不幸的是，这并不像添加它要求的实例那么简单：如果您为 (a -> a) -> 编写一个实例一个-> a，Haskell 将此解释为任何特定 a 的实例，而 Church 数字的正确解释是一个适用于任意 的多态函数>一个。

换句话说，您希望您的 show 函数是这样的：

showChurch n = show $ n (+1) 0

如果您确实愿意，您可以像这样实现 Show 实例：

instance (Show a, Num a) => Show ((a -> a) -> a -> a) where
    show n = show $ n (+1) 0

并添加 {-#LANGUAGEFlexibleInstances#-} 到文件的第一行。或者您可以实现类似的方法将它们转换为常规数字

> churchToInt c1
1
> showChurch c1
"1"

等。

Answer 2

编辑：剧透警报，如评论中所述

或者，您可以有一个教堂数字的类型，如下所示：

data Church x = Church ((x -> x) -> x -> x)

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

-- Hack to not clash with the standard succ
succ_ :: Church x -> Church x
succ_ (Church n) = Church (\f x -> (f (n f x)))

instance (Num x) => Show (Church x) where
  show (Church f) = show $ f (1 +) 0