使用foldr确定长度

Question

我想了解我正在参加的课程的讲义中的一部分。它将长度函数定义为：

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

有人可以解释我是如何工作的吗？我无法围住它。

Answer 1

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

考虑使用成上下文，foldr发生在3个参数：一个功能（即在一个接受一个列表和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基本上就是这样，但除了硬编码空列表[]和配对构造函数:进入右侧，我们改为使用一些任意常量和作为参数提供的函数。我有时喜欢把这些论点fakeCons和fakeNil（cons和nil是:运营商和Lisp编程语言[]不变的名称），因为从某种意义上说你是“复制”列表中，但使用假构造函数：

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是一个函数，有两个参数：列表中的一个元素，和部分解决：解决您的问题，为那些看起来则传递到f元素的右边的元素列表。然后产生一个“更大的一个元素”的解决方案。

所以在length情况：

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

这种关于foldr的思考方式非常强大，不应低估。基本上，在您作为foldr的第一个参数传递的函数中，允许您假设您尝试解决的问题已经为所有比您处理的列表短的列表解决。你所有的参数函数必须做的是计算一个长度为一个元素的列表的答案。