我已经看到了教堂数字的以下数据构造函数
data Nat = Zero | Succ Nat deriving Show
但这是一元数。我们如何以这种方式在 Haskell 中实现二进制数的数据构造函数？
我试过这个：
data Bin = Zero | One | BinC [Bin] deriving Show
在此之后我们可以得到，十进制 5 编码为BinC [One,Zero,One]
但我想我在这里遗漏了一些东西。我的解决方案似乎不如教会的解决方案聪明。毫不奇怪，我不是教会。稍微思考一下，我发现我的解决方案依赖于列表，而 Nat 不依赖于任何像列表这样的外部结构。
我们是否也可以编写一个类似于 Church 的解决方案，对二进制数使用 Succ 类型构造函数？如果是，如何？我尝试了很多，但似乎我的大脑无法摆脱对列表或其他类似结构的需求。
我能想到的最接近的是
λ> data Bin = LSB | Zero Bin | One Bin
λ| -- deriving Show
这使得构建二进制数成为可能
λ> One . One . Zero . Zero . One . One $ LSB
One (One (Zero (Zero (One (One LSB)))))
人们也可以想象一个解码功能的工作原理（Ingo 在评论中建议的更好的版本）
λ> let toInt :: (Integral a) => Bin -> a
λ| toInt = flip decode 0
λ| where decode :: (Integral a) => Bin -> a -> a
λ| decode LSB value = value
λ| decode (Zero rest) value = decode rest (2*value)
λ| decode (One rest) value = decode rest (2*value + 1)
然后可用于将二进制数解码为整数。
λ> toInt (Zero . One . One . One . Zero . Zero . One $ LSB)
57
您想要完成的困难在于您需要“从里到外”阅读二进制数或可以这么说。要知道最高有效数字的值，您需要知道数字中有多少位数字。如果您要以“反向”形式编写二进制数 - 即最外面的数字是最低有效数字，那么事情会更容易处理，但是当您创建它们并使用默认实例将它们打印出来时，这些数字会向后看的Show。
这不是一元数字的问题的原因是因为没有“最低有效数字”，因为所有数字都具有相同的值，因此您可以从任一方向解析数字，您将得到相同的结果。
为了完整起见，这里是同一件事，但最外面的数字是最低有效数字：
λ> data Bin = MSB | Zero Bin | One Bin
λ| -- deriving Show
这看起来很像以前，但是你会注意到当解码功能被实现时，
λ> let toInt = flip decode (1,0)
λ| where
λ| decode (One rest) (pos, val) = decode rest (pos*2, val+pos)
λ| decode (Zero rest) (pos, val) = decode rest (pos*2, val)
λ| decode MSB (_, val) = val
数字是倒着写的！
λ> toInt (Zero . Zero . Zero . One . Zero . One $ MSB)
40
但是，这更容易处理。例如，我们可以根据具体情况添加两个二进制数。（警告：很多案例！）
λ> let add a b = addWithCarry a b False
λ| where
λ| addWithCarry :: Bin -> Bin -> Bool -> Bin
λ| addWithCarry MSB MSB True = One MSB
λ| addWithCarry MSB MSB False = MSB
λ| addWithCarry MSB b c = addWithCarry (Zero MSB) b c
λ| addWithCarry a MSB c = addWithCarry a (Zero MSB) c
λ| addWithCarry (Zero restA) (Zero restB) False = Zero (addWithCarry restA restB False)
λ| addWithCarry (One restA) (Zero restB) False = One (addWithCarry restA restB False)
λ| addWithCarry (Zero restA) (One restB) False = One (addWithCarry restA restB False)
λ| addWithCarry (One restA) (One restB) False = Zero (addWithCarry restA restB True)
λ| addWithCarry (Zero restA) (Zero restB) True = One (addWithCarry restA restB False)
λ| addWithCarry (One restA) (Zero restB) True = Zero (addWithCarry restA restB True)
λ| addWithCarry (Zero restA) (One restB) True = Zero (addWithCarry restA restB True)
λ| addWithCarry (One restA) (One restB) True = One (addWithCarry restA restB True)
此时添加两个二进制数是轻而易举的事：
λ> let forty = Zero . Zero . Zero . One . Zero . One $ MSB
λ| eight = Zero . Zero . Zero . One $ MSB
λ|
λ> add forty eight
Zero (Zero (Zero (Zero (One (One MSB)))))
确实如此！
λ> toInt $ Zero (Zero (Zero (Zero (One (One MSB)))))
48
只是您收到的其他答案的附录：
您创建的数据值实际上是 Peano 数字，而不是 Church 数字。它们密切相关，但它们实际上是彼此对偶/反向的。Peano 数字是建立在从 Set 的概念中构造数字的概念之上的，在 Haskell 中，我们使用密切相关的数据类型概念来表示。
{-# LANGUAGE RankNTypes #-}
import Prelude hiding (succ)
data Peano = Zero
| Succ Peano
deriving (Show)
另一方面，教堂数字将数字编码为函数：
type Church = forall n. (n -> n) -> n -> n
zero :: Church
zero = \p -> id
succ :: Church -> Church
succ = \n p -> p . n p
现在，您可以将它们放在一起：
peano :: Church -> Peano
peano c = c Succ Zero
fold :: forall n. (n -> n) -> n -> Peano -> n
fold s z Zero = z
fold s z (Succ p) = s (fold s z p)
church :: Peano -> Church
church p = \s z -> fold s z p
因此，Church 数字本质上是 Peano 数字的折叠！并且(peano . church)是 Peano 数字的标识，尽管使用上面给出的类型，Haskell 不会让你直接这样组合它们。如果您省略类型声明，Haskell 将推断出足够通用的类型，您将能够组合它们。
在 Ralf Hinze 的 Theoretical Pearl Church numbers 中，在函数式编程的上下文中，有一个很好的差异及其相互关系的概述，两次！.
您可以进一步概括这种二元性；Peano 数字本质上是自然数的初始 F 代数，Church 数字本质上是自然数的最终/终结 F 代数。Bart Jacobs 和 Jan Rutten 的A Tutorial on (Co)Algebras and (Co)Induction对此进行了很好的介绍。
data Bit = Zero | One
data Bin = E Bit | S Bit Bin
five = S One (S Zero (E One))