在Haskell中将十进制转换为二进制

Question

我发现这段代码有效,但我不明白为什么会这样.它将Int转换为二进制表示形式.

repBinario::Int -> Int
repBinario 0 = 0
repBinario x = 10 * repBinario (x `div` 2) + x `mod` 2

我知道做什么div和mod做什么.但是,它如何将每个数字mod放在一起？

Answer 1

简而言之,它将累计结果乘以10每次迭代.

为了更清楚地了解正在发生的事情,我们可以将您的功能划分为两个更简单的功能.第一个将整数转换为二进制数字列表.然后另一个将完成困扰你的事情:将二进制数字列表连接成一个整数.

extractBinDigits :: Int -> [Int]
extractBinDigits =
  unfoldr (\x -> if x == 0 then Nothing else Just (mod x 2, div x 2))

concatDigits :: [Int] -> Int
concatDigits =
  foldr (\a b -> a + b * 10) 0

如您所见,我们只需将列表折叠乘以累加器,10然后将每个数字加到其上.

然后你的原始功能变成了这样:

repBinario :: Int -> Int
repBinario =
  concatDigits . extractBinDigits

现在,我们可以检查和重复使用我们程序中更精细的部分,为我们提供更大的灵活性.例如,通过添加另一个简单函数,您现在可以一次性将整数转换为字符串:

showDigits :: [Int] -> String
showDigits =
  reverse . map (chr . (+ 48))

repStringyBinario :: Int -> String
repStringyBinario =
  showDigits . extractBinDigits

Answer 2

让我们来看一个例子,然后:

repBinario 5

替代定义repBinario 5:

10 * repBinario (5 `div` 2) + 5 `mod` 2

减少div和mod:

10 * repBinario 2 + 1
                    ^

在这里,我们制作了第一个数字,标有^.

替代定义repBinario 2:

10 * (10 * repBinario (2 `div` 2) + 2 `mod` 2) + 1
                                                 ^

减少div和mod:

10 * (10 * repBinario 1 + 0) + 1
                          ^    ^

替代定义repBinario 1:

10 * (10 * (10 * repBinario (1 `div` 2) + 1 `mod` 2) + 0) + 1
                                                       ^    ^

减少div和mod:

10 * (10 * (10 * repBinario 0 + 1) + 0) + 1
                                ^    ^    ^

替代定义repBinario 0:

10 * (10 * (10 * 0 + 1) + 0) + 1
                     ^    ^    ^

降低:

101

在每一步,(`mod` 2)得到至少显著二进制数字,和(`div` 2)移位数向右时,丢弃所述数字和递归传递数的其余部分divBinario.最后,我们做了相反的过程:(+ d)将当前数字的结果,并且(* 10)将这个数字向左因此我们可以添加更多的数字.

你得到的是一个十进制数,看起来与原始输入的二进制表示相同.

如果你删除乘法10,你得到popCount一个函数,它给你一个数字的总体数 - 1它的二进制表示中的位数:

popCount 0 = 0
popCount x = popCount (x `div` 2) + x `mod` 2

popCount 5  ==  2

Answer 3

我认为最好手动计算一个小值的这个函数 - 这是可能的,因为这是一个纯函数,因此你可以用它的定义(即右手边)代替左手边 - 这个花哨的计算机科学词功能是"参考透明度".

repBinario 24 = 10 * repBinario (24 `div` 2) + 24 `mod` 2
              = 10 * repBinario 12 + 0
              = 10 * (10 * repBinario (12 `div` 2) + 12 `mod` 2)
              = 100 * repBinario 6 + 0
              = 100 * (10 * repBinario (6 `div` 2) + 6 `mod` 2)
              = 1000 * repBinario 3 + 0
              = 1000 * (10 * repBinario (3 `div` 2) + 3 `mod` 2)
              = 10000 * repBinario 1 + 1000 * 1
              = 10000 (10 * repBinario (1 `div` 2) + 1 `mod` 2) + 1000
              = 10000 (10 * repBinario 0 + 1) + 1000
              = 10000 (10 * 0 + 1) + 1000
              = 10000 * 1 + 1000
              = 11000

在这些步骤中,我只是通过其定义评估函数,并使用整数加法/乘法服从分布律的事实.