哈斯克尔的教堂数​​字

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.

然后,您获得的错误是通知您已经评估了没有已Show定义实例的类型的表达式.Modulo一些措辞,这是所有错误信息说:

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

类型((t -> t1) -> t -> t1)是您评估的表达式的推断类型.这是教会数字1的有效类型,尽管教会数字的"正确"类型实际上应该是(a -> a) -> a -> a.

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

它隐含地使用该print函数来显示值.通常,这会告诉您程序中的错误发现位置,但在这种情况下,它表示<interactive>:1:0-1错误是由REPL中的表达式引起的.

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

这只是建议你可以通过定义它期望的实例来修复错误.

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

换句话说,您希望您的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

并添加{-#LANGUAGE FlexibleInstances#-}到文件的第一行.或者你可以实现类似的东西,将它们转换为常规数字

> churchToInt c1
1
> showChurch c1
"1"

等等

Answer 2

编辑:Spoiler Alert,如评论中所述

或者,您可以使用教会数字类型,如下所示:

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