将二进制转换为十进制 Haskell

Question

我需要一个程序，可以让我输入二进制数，然后将其转换为十进制数并返回给我。

binToDec :: Integer -> Integer

binToDec 1110101011111111000000111100001010101011110010000001 = 4134096010394753

binToDec 111111111111111111111111111111111111111111111111111111111111111 =  9223372036854775807 

我希望以上示例的编译时间能在5秒内完成。

我已经设法做到了，但问题是它始于一个整数列表：

binToDec l = sum $ map (2^) $ findIndices (==1) $ reverse l

- mathandtic

---

在处理这个“二进制数”的时候，你不应该使用一个 Integer 类型。一个字符串输入或者一个布尔值列表会更加合适。 - Bergi

需要在5秒钟内编译上述示例吗？听起来非常可疑，好像你正在滥用编译器进行转换。请不要这样做。- 如果你真的需要在Haskell源代码中写入二进制，请使用-XBinaryLiterals扩展。 - leftaroundabout

Answer 1

由于“十进制”数字仅包含零和一，因此我们可以使用递归来解决这个问题：

bintodec :: Integral i => i -> i
bintodec 0 = 0
bintodec i = 2 * bintodec (div i 10) + (mod i 10)

这里我们使用“div i 10”将数字向右移动一位。我们使用递归和乘以2来使用二进制表示。我们还使用“mod i 10”获取最后一位数字，然后将其添加到数字中。

如前所述，这种方法并不是非常安全，例如它也会为“bintodec 10010202010”生成一个数字，在这种情况下，我们可以返回一个Maybe i ，其中包含：

bintodec :: Integral i => i -> Maybe i
bintodec 0 = Just 0
bintodec i | last < 2 = fmap (\x -> 2*x + last) (bintodec (div i 10))
           | otherwise = Nothing
    where last = mod i 10

这将产生以下结果：

Prelude> bintodec 1110101011111111000000111100001010101011110010000001
Just 4134096010394753
Prelude> bintodec 11101010111111110000001111000010101014011110010000001
Nothing

然而，最好使用[Bool]，因为这将强制我们不会提供无效的二进制字符串。在这种情况下，我们可以使用：

bintodec :: [Bool] -> Int
bintodec = foldr (\x y -> fromEnum x + 2*y) 0

- Willem Van Onsem

---

它可以没有 Maybe i 吗？ - mathandtic

@mathandtic：那是程序的第一个版本。你可以选择其中任何一个。但第二个更加安全。 - Willem Van Onsem

我认为在你的例子 bintodec = foldr (\x y -> fromEnum x + 2*y) 0 中，你需要使用 foldl 而不是 foldr。 - Troydm

Answer 2

decToBin :: Integer -> Integer
decToBin = convert' 10 2

binToDec :: Integer -> Integer
binToDec = convert' 2 10

convertAny :: Integer -> Integer -> Integer -> Integer
convertAny from to = convert' 10 to . convert' from 10

convert' :: Integer -> Integer -> Integer -> Integer
convert' from to | validBase from && validBase to = go
  where
    go 0 = 0
    go k | valid = r + from * go q
         | otherwise =
           error $ "Invalid digit (" ++ show d ++ ") for base " ++ show from
       where
         valid = d < from
         d = k `mod` 10
         (q,r) = k `divMod` to
    validBase b = b >=2 && b <= 10
convert' _ _ = error "Bases must be between 2 and 10.

- Christian Brolin