haskell - 如何在 Haskell 中实现二进制数

Question

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

data Nat = Zero | Succ Nat deriving Show

但这是一元数。
我们如何以这种方式在 Haskell 中实现二进制数的数据构造函数？

我试过这个:

data Bin = Zero | One | BinC [Bin] deriving Show

在此之后我们可以得到，十进制 5 编码为 BinC [One,Zero,One]
但我想我在这里遗漏了一些东西。我的解决方案似乎不如教会的解决方案聪明。毫不奇怪，我不是教会。稍微思考一下，我发现我的解决方案依赖于列表，而 Nat 不依赖于任何像列表这样的外部结构。

我们是否也可以编写一个类似于 Church 的解决方案，对二进制数使用 Succ 类型构造函数？如果是，如何？我尝试了很多，但似乎我的大脑无法摆脱对列表或其他类似结构的需求。

Answer 1

我能想到的最接近的是

λ> 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