haskell - 自定义 'fold' 函数需要计数器

Question

我的家庭作业进行得非常顺利，直到我偶然发现了最后一项任务。
首先，我必须定义一个自定义 List结构体:

data List a = Nil | Cons a (List a) deriving Show

另一个任务是编写自定义 fold功能:

foldList :: (a -> b -> b) -> b -> List a -> b
foldList f b Nil        = b
foldList f b (Cons a l) = f a (foldList f b l)

第二个参数是在列表末尾使用的值(在 Nil 元素处)。

我还必须写一个函数 prodList将提供的列表的每个元素相互乘以:

prodList :: List Int -> Int
prodList = foldList (\x y -> x * y) 1

1最后是乘法的中性元素。因此，它对计算没有影响。

然而，最后一个对我来说很难解决。
我必须写一个函数 binList计算表示二进制数的列表的十进制值。最低有效位是列表的第一个元素，因此二进制数被反转。
一个给定的例子是 binList (Cons 1 (Cons 0 (Cons 0 (Cons 0 (Cons 1 Nil))))) 的结果应该是 19(因为 (10001)_2 是 (19)_10)。然而，列表 [1,1,0,1] 的结果应该是 (1011)_2=(11)_10)。
分配的罪魁祸首是，我们必须使用 foldList .

我知道如何计算每个数字，但我很难找到一种方法来找出哪个索引 i我目前在:

binList :: List Int -> Int
binList = foldList (\x y -> 2^i*x + y)

在 Haskell 中可能有一个很好的 curry 方法来解决这个问题。你能向我解释一下你将如何解决这个任务吗？

Answer 1

如果你要写出计算，它看起来像这样:

x0 + 2 * x1 + 4 * x2 + 8 * x3 + ...

这可能表明您需要使用索引，但如果您对这个表达式进行因式分解，则会得到以下结果:

x0 + 2 * (x1 + 2 * (x2 + 2 * (x3 ...

你现在看到它如何写成折叠了吗？请注意，有一个类似这样的自相似性:

x + 2 * x'

希望这对你来说已经足够了:)