自定义'折叠'功能需要计数器

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在端部是multplication的中性元素.因此它对计算没有影响.

不过,最后一个对我来说很难解决.
我必须编写一个函数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中可能有一种很好的咖喱方式可以解决这个问题.你能解释一下如何解决这项任务吗？

Answer 1

如果你要写出计算,它将如下所示:

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

这可能表明你需要使用索引,但是如果你对这个表达式进行分解,你会得到这个:

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

你看到它现在如何写成折叠吗？请注意,存在一种类似于此的自相似性:

x + 2 * x'

希望这足以暗示你:)