haskell - 使用 foldr 定义长度

Question

我试图理解我正在上课的讲义中的一部分。它将长度函数定义为：

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

有人可以解释一下这是如何工作的吗？我无法绕开它。

Answer 1

首先，类型foldr：(a -> b -> b) -> b -> [a] -> b

将用法纳入上下文，foldr接受 3 个参数：一个函数（接受a.列表的一个元素和b.一个累加器，并返回累加器）、累加器的起始值和一个列表。foldr通过列表应用函数后返回累加器的最终结果。

至于这段代码：

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

如您所见，它缺少列表 - 因此右侧的返回值是一个函数，它将接收一个列表并产生一个 Int （与 相同的类型0）。类型：[a] -> Int.

至于右手边是什么意思：(\_ n -> 1 + n) 0

\表示声明一个未命名的函数

_表示忽略列表中的元素（对应a于 的类型foldr）。如您所知，foldr将遍历列表并将函数应用于每个元素。这是传递给函数的元素。我们没有在length函数中使用它，所以我们表示它应该被忽略。

n是作为累加器传入的 Int 的参数。

->意味着返回

1 + n将增加累加器。您可以想象返回值被传回foldr并foldr保存该值以传递给函数的下一次调用(\_ n -> 1 + n)。

括号外面是计数器的0起始值。

Answer 2

功能foldr是用右结合运算符折叠列表，如果使用运算符，您可以很容易地理解该函数的作用(+)，（该函数与 具有相同的行为sum）：

foldr (+) 0 [1,2,3,4,5] = 1+(2+(3+(4+(5+0))))

对于您的长度函数，它相当于：

foldr (\_ n -> 1 + n) 0 [1,2,3,4,5] = 1+(1+(1+(1+(1+0))))

这就是foldr为了

Answer 3

有几种等效的方法可以理解它。第一个：foldr f z [1, 2, 3, 4, ..., n]计算以下值：

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

所以在你的情况下：

length [1,2,3,4] = foldr (\_ n -> 1 + n) 0 [1,2,3,4]  
                 = (\_ n -> 1 + n) 1 ((\_ n -> 1 + n) 2 ((\_ n -> 1 + n) 3 ((\_ n -> 1 + n) 4 0)))
                 = (\_ n -> 1 + n) 1 ((\_ n -> 1 + n) 2 ((\_ n -> 1 + n) 3 (1 + 0)))
                 = (\_ n -> 1 + n) 1 ((\_ n -> 1 + n) 2 (1 + (1 + 0)))
                 = (\_ n -> 1 + n) 1 (1 + (1 + (1 + 0)))
                 = 1 + (1 + (1 + (1 + 0)))
                 = 1 + (1 + (1 + 1))
                 = 1 + (1 + 2)
                 = 1 + 3
                 = 4

另一种是从这个函数开始，它复制一个列表：

listCopy :: [a] -> [a]
listCopy [] = []
listCopy (x:xs) = x : listCopy xs

这可能看起来像一个微不足道的函数，但foldr基本上就是这样，但除了将空列表[]和对构造函数硬编码:到右侧之外，我们改为使用一些作为参数提供的任意常量和函数。我有时喜欢将这些参数称为fakeConsand fakeNil( consand是 Lisp 语言中的运算符和常量nil的名称)，因为从某种意义上说，您是在“复制”列表，但使用了假构造函数：:[]

foldr fakeCons fakeNil [] = fakeNil
foldr fakeCons fakeNil (x:xs) = fakeCons x (subfold xs)
    where subfold = foldr fakeCons fakeNil

因此，根据这种解释，您的length函数是“复制”一个列表，除了它使用的不是空列表0，而是:丢弃元素并在运行总数中加 1。

这里还有第三种解释foldr f z xs：

1. z是列表为空时您的问题的解决方案。
2. f是一个接受两个参数的函数： list 的一个元素和一个部分解决方案：对于出现在传递给的元素右侧的元素列表的问题的解决方案f。 f然后产生一个“更大的一个元素”的解决方案。

所以在以下情况下length：

1. 空列表的长度为 0，因此您使用 0 作为foldr.
2. 如果 的长度xs为n，则 的长度x:xs为n+1。这就是 , 的第一个参数foldr正在\_ n -> n + 1做的事情：它正在计算列表的长度，作为参数给出列表的第一个元素（在这种情况下我们忽略）和列表其余部分的长度 ( n)。

这种思考方式foldr非常强大，不容小觑。基本上，在您作为第一个参数传递给 的函数中foldr，您可以假设您尝试解决的问题已经解决了所有比您正在处理的列表短的列表。那么，您的参数函数所要做的就是为一个元素更长的列表计算答案。