自定义 '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'

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

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

Custom 'fold' function needs counter

counter

haskell

fold