function - 使用 Horners 算法在 Haskell 中进行二进制到十进制的转换

Question

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

函数类型为[Bool] -> Int。

我遵循的算法是:

Horners算法可视化解释:

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

然后在这种情况下binToDecList (x:xs) = binToDecList' x 0我如何处理第一个元素，无论这是 True 还是 False。

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](第三个参数是某个内容的列表)必须是要传递给 Horner 算法的 Bool 列表。这意味着类型变量 a 必须是 Bool。

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

foldl 的工作原理是从左侧遍历列表(即，从其头部开始)，并以某种方式将到目前为止的结果与列表中的下一个元素组合起来。第二个参数通常命名为“z”，表示“零”或折叠过程的种子值。当foldl到达列表末尾时，它返回累积值。

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

想想霍纳的算法是如何进行的。图表中路径拐角处的数字代表上一段中“到目前为止的结果”。我们知道b是Int，a是Bool，所以函数传递给foldl 必须将 Bool 转换为 Int 并将其与结果结合起来。

霍纳算法的第一步似乎是一个特殊情况，需要以不同的方式处理，但 foldl 始终使用相同的函数。如果您想象一开始就通过看不见的水平移动(即乘以二)来“启动泵”，我们可以将这些类型像拼图一样拼在一起。没关系，因为两倍零仍然是零。

因此，就foldl而言，Horner的算法是

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。