使用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. f然后产生一个"一个更大的元素"的解决方案.

所以在以下情况下length:

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

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