如何在 Haskell 中实现二进制数

我看到了以下教堂数字的数据构造函数

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