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,列表的长度.基本上,fold会忽略列表中的每个元素,只是为每个元素添加一个累加器,给出长度.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