Haskell中的二进制到十进制转换使用Horners算法

Question

我试图在这里实现一个函数，它取一个表示二进制数的Bool列表，如[True, False, False]，并根据Horners方法将其转换为相应的十进制数。

功能类型是[Bool] -> Int。

我遵循的算法是：

Horners算法视觉说明：

到目前为止，我已经实现了逻辑，首先它将检查列表是否为空或列表[True]中的任何一个元素，将给出1，[False]将给出0。

然后在这种情况下binToDecList (x:xs) = binToDecList' x 0我做了什么来对待第一个元素是否是真或假。

binToDecList :: [Bool] -> Int
binToDecList []      = error "Empty List"
binToDecList [True]  = 1
binToDecList [False] = 0
binToDecList (x:xs)  =  binToDecList' x 0 
binToDecList' x d | x == True = mul (add d 1)
                  | otherwise = mul (add d 0)

add :: Int -> Int -> Int
add x y = x + y

mul :: Int -> Int
mul x = x * 2

我想在下一次迭代中使用binToDecList'的结果，在列表的下一个元素上递归调用它自己。如何存储结果，然后递归地将其应用于列表的下一个元素。任何形式的帮助将不胜感激。

Answer 1

foldl的类型*告诉我们它必须如何工作。

foldl :: (b -> a -> b) -> b -> [a] -> b

很明显[a]，第三个参数是一个列表的东西，必须是Bool的列表，交给Horner的算法。这意味着类型变量a必须是Bool。

类型变量b表示可能不同的类型。我们正在尝试将[Bool]转换为Int，所以Int对于b来说是一个不错的猜测。

foldl通过从左侧咀嚼一个列表（即从头开始）并以某种方式将结果与列表中的下一个元素组合起来。第二个参数通常将z命名为“零”或折叠过程的种子值。当foldl到达列表的末尾时，它返回累计值。

我们可以在语法上看到第一个参数是某个函数，它对b类型的项执行某些操作，并输入a以生成b。现在，一个忽略a项目的函数无条件地导致b适合但不会很有趣。

想想Horner的算法是如何进行的。图表中路径肘部的数字代表前一段中的“到目前为止”的名义“结果”。我们知道b是Int而a是Bool，因此传递给foldl的函数必须将Bool转换为Int并将其与结果相结合。

Horner算法的第一步似乎是需要以不同方式处理的特殊情况，但foldl一直使用相同的功能。如果你想象一下“用水不可见的水平移动（即乘以2）”来开始，我们就可以使这些类型像拼图一样融合在一起。这很好，因为两次零仍然是零。

因此，就foldl而言，霍纳的算法是

horners :: [Bool] -> Int
horners = foldl f 0
  where f x b =
          let b' = fromEnum b
          in 2*x + b'

请注意，2*x + b'结合了后续的水平和垂直移动。

这也暗示了如何以直接递归方式表达它。

horners' :: [Bool] -> Int
horners' [] = 0
horners' l  = go 0 l
  where -- over then down
        go x [] = x
        go x (b:bs) =
          let b' = fromEnum b
          in go (2*x + b') bs

这里内部go循环执行左侧折叠并将每个下一个Bool与i中的结果相结合。

---

*教学简化：实际类型将列表类型概括为Foldable。