haskell - Haskell高阶函数计算长度

Question

我不明白这里发生了什么？有人可以解释一下这段代码吗？这个函数如何计算长度？

callength = foldr (\_ n -> 1 + n) 0

为什么它使用 lambda、下划线、下划线和 n 之间的空格以及右侧的零？

Answer 1

(\_ n -> 1 + n) 简单地表示一个函数，它接受两个参数，并返回比它的第二个参数多一个。下划线仅表示忽略参数。作为比较，作为不使用通配符模式（下划线）的顶级声明，此函数如下所示：

foo x n = 1 + n

现在，这是一个示例列表：

[1, 2, 3, 4]

这实际上只是语法糖：

1 : 2 : 3 : 4 : []

foldr所做的是递归地用(:)给定的函数替换每个，并用[]函数后面的参数（零）替换。所以，foldr f z [1, 2, 3, 4]对于任何f和z看起来像这样：

f 1 (f 2 (f 3 (f 4 z)))

（这就是为什么foldr (:) []只返回你给它的同一个列表——它最终重建了原始列表结构。）

在这种情况下，使用函数foo和零 0，它看起来像：

foo 1 (foo 2 (foo 3 (foo 4 0)))

我们知道它foo忽略了它的第一个参数，并返回一个比它的第二个参数多一个。所以这与以下内容相同：

1 + (1 + (1 + (1 + 0)))

这是4，列表的长度。基本上，折叠忽略列表中的每个元素，并且只为每个元素添加一个累加器，给出长度。0用于结束整个过程，因为空列表的长度为0。

为了更详细地了解这一点，我们可以逐步展开每个调用：

foldr foo 0 (1 : 2 : 3 : 4 : [])
foo 1 (foldr foo 0 (2 : 3 : 4 : []))
1 + foldr foo 0 (2 : 3 : 4 : [])
1 + foo 2 (foldr foo 0 (3 : 4 : []))
1 + 1 + foldr foo 0 (3 : 4 : [])
1 + 1 + foo 3 (foldr foo 0 (4 : []))
1 + 1 + 1 + foldr foo 0 (4 : [])
1 + 1 + 1 + foo 4 (foldr foo 0 [])
1 + 1 + 1 + 1 + foldr foo 0 []
1 + 1 + 1 + 1 + 0
1 + 1 + 1 + 1
1 + 1 + 2
1 + 3
4