Haskell Decimal to Binary

Question

我正在尝试构建一个将十进制(Int)转换为二进制数的函数。不幸的是，除了java之外，在haskell中不可能将int除以2。我是函数式编程的新手，所以这个问题可能是微不足道的。到目前为止，我找不到其他解决这个问题的方法，但这是我的第一次尝试：

 fromDecimal :: Int -> [Int]

fromDecimal 0 = [0]
fromDecimal n = if (mod n 2 == 0) then 
                do

                0:fromDecimal(n/2) 

                else 
                do  
                1:fromDecimal(n/2) 

我在这里得到了一个java实现，就像我之前做的那样：

   public void fromDecimal(int decimal){
    for (int i=0;i<values.length;i++){

        if(decimal % 2 = 0)
        values[i]=true ; 
        decimal = decimal/ 2;
        else {values[i]= false;
        }       }
}

希望这将有助于找到解决方案！

Answer 1

你不能在Haskell中定义整数-- /不是用整数定义的！对于整数除法，使用div函数，但在您的情况下，更适合的是mod免费附带的divMod。

此外，你会得到相反的输出，所以你可以在那之后手动reverse它，或者使用更节省内存的版本与累加器：

decToBin :: Int -> [Int]
decToBin = go [] where
   go acc 0 = acc
   go acc n = let (d, m) = n `divMod` 2 in go (m : acc) d

go会给你一个空的0列表。如果列表为空，您可以手动添加：

decToBin = (\l -> if null l then [0] else l) . go [] where ...

Answer 2

仔细考虑你的算法是如何工作的。它从2⁰开始，因此它将生成与我们通常认为的位相反的位，即首先生成最低有效位。您的算法只能表示非负的二进制整数。

fromDecimal :: Int -> [Int]
fromDecimal d | d < 0     = error "Must be non-negative"
              | d == 0    = [0]
              | otherwise = reverse (go d)
  where go 0 = []
        go d = d `rem` 2 : go (d `div` 2)

在Haskell中，当我们反向生成一个列表时，继续这样做，但在最后reverse结果。这样做的原因是拼凑一个列表(用:在顶部粘合新项目)有一个固定的成本，而最后的reverse有一个线性成本-但是附加++有一个二次成本。

常见的Haskell风格是有一个名为go的私有内循环，当外部函数对其参数满意时，它将应用该内循环。基本情况是在d达到零时使用空列表终止。否则，我们取当前的余数模2，然后将d减半并截断。

如果没有0的特殊情况，fromDecimal 0将是空列表而不是[0]。

Answer 3

二进制数通常是字符串，并不真正用于计算。字符串也不那么复杂。

二进制数的模式与其他任何数字都一样。它会以更快的速度重复。只需要很小的集合即可生成多达256 (0-255)个二进制数。该模式可以系统地扩展到更多。起始模式为4，0-3

bd = ["00","01","10","11"]

将它们组合成更大数字的函数是

d2b n = head.drop n $ [ d++e++f++g | d <- bd, e <- bd, f <- bd, g <- bd]

d2b 125

"01111101“

如果不清楚如何扩展，那么

bd = ["000","001","010","011","100","101","110","111"]

将提供最多4096个二进制位(0-4095)。其他的都保持不变。

如果不明显，db2函数使用4对二进制数，因此集合中的4对二进制数。(2^8) -1或(2^12) -1是您得到的数量。

顺便说一句，列表理解是糖衣do结构。

生成上面的模式

[ a++b | a <- ["0","1"], b <- ["0","1"] ]

"00"，"01"，"10"，"11“

和

[ a++b++c | a <- ["0","1"], b <- ["0","1"], c <- ["0","1"] ]

"000"，"001"，"010"，"011"，"100"，"101"，"110"，"111“

更一般地说，一种模式和一种功能可以服务于此目的

b2 = ["0","1"]
b4 = [ a++b++c++d | a <- b2, b <- b2, c <- b2, d <- b2]
b4

0000，"0001"，"0010"，"0011"，"0100"，"0101"，"0110"，"0111"，"1000"，"1001"，"1010"，"1011"，"1100"，"1101"，"1110"，"1111“

bb n = head.drop n $ [ a++b++c++d | a <- b4, b <- b4, c <- b4, d <- b4]
bb 32768

"1000000000000000“

bb 65535

"1111111111111111“

在Haskell中使用减法直接从十进制计算二进制

cvtd n (x:xs) | x>n  = 0:(cvtd  n xs)
              | n>x  = 1:(cvtd (n-x) xs)
              | True = 1:[0|f<-xs]

使用所需的任意位数，例如10位。

cvtd 639 [2^e|e<-[9,8..0]]

1，0，1，1，1，1，1，1，1