如何实现在Haskell二进制数 [英] How to implement Binary numbers in Haskell

问题描述

我已经看到了Church数以下数据构造

I have seen the following data constructor for Church numerals

data Nat = Zero | Succ Nat deriving Show

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

But this is unary numbers. How do we implement a data constructor for Binary numbers in Haskell in this way?

我已经试过这样：

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

在此，我们可以得到，小数5间codeD为 BINC [大，零，一]

After this we can get, decimal 5 encoded as BinC [One,Zero,One]

但我觉得我在这里失去了一些东西。我的解决方案似乎并不像教会的解决方案一样聪明。毫不奇怪，我不是教堂。思维点点，我发现我的解决方案取决于列表中，而NAT不依赖于像列表中的任何这样的外部结构。

But I think I am missing something here. My solution seems not as clever as the Church's solution. No surprise, I am not Church. Little bit of thinking, I found that my solution depends upon list, whereas the Nat doesn't depend upon any such external structure like list.

我们能写一个解决方案，类似教会的使用二进制数过一SUCC类构造函数？如果是的话，怎么样？我尝试了很多，但似乎我的大脑无法摆脱的需求列表，或者其他类似的结构。

Can we write a solution that is similar to Church's using a Succ type constructor for Binary numbers too? If yes, how? I tried a lot, but it seems my brain cannot get rid of the need of list or some other such structure.

推荐答案

我能想到的最接近的将是这样

The closest I can think of would be something like

λ> data Bin = LSB | Zero Bin | One Bin
λ|  -- deriving Show

此使得有可能构建二进制数做只是

This makes it possible to construct binary numbers doing just

λ> One . One . Zero . Zero . One . One $ LSB
One (One (Zero (Zero (One (One LSB)))))

你也可以想像解码功能上（在评论由英戈建议更好的版本）

One could also imagine a decoding function working on the principle of (much better version suggested by Ingo in the comments)

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

然后可使用脱code进行二进制数的整数倍。

Which can then be used to decode a binary number to an integral number.

λ> toInt (Zero . One . One . One . Zero . Zero . One $ LSB)
57

---

与你想要完成的任务的困难是，你需要阅读二进制数内向外还是这么说。要知道最显著数字的值，你需要知道你有多少个数字有多少。如果你是反转写你的二进制数 - 也就是最外层的数字是最显著的数字，那么事情就好办了很多，但数字会倒着看，当你创建它们并使用默认实例打印出来的显示。

究其原因，这是不是一元数的问题是因为没有最低显著数字，因为所有的数字具有相同的值，这样你就可以从任一方向解析的数量，你会得到相同的结果。

The reason this is not a problem with unary numbers is because there is no "least significant digit" since all digits have the same value, so you can parse the number from either direction and you will get the same result.

有关完整，这里是同样的事情，但最外面的数字是最低显著位：

For completeness, here is the same thing but with the outermost digit being the least significant digit:

λ> data Bin = MSB | Zero Bin | One Bin
λ|   -- deriving Show

这看起来pretty多像以前一样，但你会发现，当解码功能的实现，

That looks pretty much like before, but you'll notice that when the decoding function is implemented,

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

然而，这是一个更容易处理。例如，我们可以根据具体情况逐案添加两个二进制数。 （警告：很多情况下）

However, this is a lot easier to handle. We can for example add two binary numbers on a case-by-case basis. (Warning: lots of cases!)

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

在这一点增加了两个二进制数是一件轻而易举的：

At which point adding two binary numbers is a breeze:

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

这篇关于如何实现在Haskell二进制数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！