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

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]，第三个参数是某物的列表，必须是Bool的列表才能交给霍纳算法。这意味着类型变量 a 必须是 Bool.

类型变量 b 表示可能不同的类型。我们正在尝试将 [Bool] 转换为 Int，因此 Int 是对 b.

的合理猜测

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

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

想想霍纳的算法是如何进行的。图中路径肘部的数字代表上一段中概念性的“到目前为止的结果”。我们知道b是Int，a是Bool，所以传给foldl的函数必须把Bool转成Int 并将其与结果合并。

Horner 算法的第一步似乎是一个特殊情况，需要以不同方式处理，但 foldl 自始至终都使用相同的函数。如果您想象以不可见的水平移动（即，乘以二）开始“启动泵”，我们可以让这些类型像拼图一样组合在一起。没关系，因为零的两倍仍然是零。

因此，就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.

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

Binary to Decimal Conversion in Haskell using Horners Algorithm

binary

haskell

function

data-conversion