任何人都可以解释它是如何foldr工作的吗？
举这些例子：
Prelude> foldr (-) 54 [10, 11]
53
Prelude> foldr (\x y -> (x+y)/2) 54 [12, 4, 10, 6]
12.0
我对这些处决感到困惑。有什么建议么？
问问题
89041 次
11 回答
166
理解 foldr 的最简单方法是重写你要折叠的列表而不加糖。
[1,2,3,4,5] => 1:(2:(3:(4:(5:[]))))
现在foldr f x所做的是它:用f中缀形式替换每个，并[]用x并评估结果。
例如：
sum [1,2,3] = foldr (+) 0 [1,2,3]
[1,2,3] === 1:(2:(3:[]))
所以
sum [1,2,3] === 1+(2+(3+0)) = 6
于 2009-11-19T13:32:32.003 回答
101
foldr从列表的右端开始，并使用您提供的函数将每个列表条目与累加器值组合起来。结果是累加器在所有列表元素中“折叠”后的最终值。它的类型是：
foldr :: (a -> b -> b) -> b -> [a] -> b
从这里你可以看到列表元素（类型a）是给定函数的第一个参数，累加器（类型b）是第二个。
对于您的第一个示例：
Starting accumulator = 54
11 - 54 = -43
10 - (-43) = 53
^ Result from the previous line
^ Next list item
所以你得到的答案是 53。
第二个例子：
Starting accumulator = 54
(6 + 54) / 2 = 30
(10 + 30) / 2 = 20
(4 + 20) / 2 = 12
(12 + 12) / 2 = 12
所以结果是 12。
编辑：我的意思是添加，这是有限列表。 foldr也可以在无限列表上工作，但我认为最好先了解有限情况。
于 2009-11-18T17:47:55.730 回答
44
foldr它有助于理解和之间的区别foldl。为什么foldr叫“对折”？
最初我以为是因为它从右到左消耗元素。然而，两者都foldr从左到右foldl使用列表。
foldl从左到右计算（左关联）foldr从右到左计算（右关联）
我们可以通过一个使用关联性很重要的运算符的示例来明确这种区别。我们可以使用一个人类示例，例如运算符“eats”：
foodChain = (human : (shark : (fish : (algae : []))))
foldl step [] foodChain
where step eater food = eater `eats` food -- note that "eater" is the accumulator and "food" is the element
foldl `eats` [] (human : (shark : (fish : (algae : []))))
== foldl eats (human `eats` shark) (fish : (algae : []))
== foldl eats ((human `eats` shark) `eats` fish) (algae : [])
== foldl eats (((human `eats` shark) `eats` fish) `eats` algae) []
== (((human `eats` shark) `eats` fish) `eats` algae)
其语义foldl是：一个人吃了一些鲨鱼，然后同一个吃过鲨鱼的人又吃了一些鱼，等等。食者是累加器。
将此与以下内容进行对比：
foldr step [] foodChain
where step food eater = eater `eats` food. -- note that "eater" is the element and "food" is the accumulator
foldr `eats` [] (human : (shark : (fish : (algae : []))))
== foldr eats (human `eats` shark) (fish : (algae : []))))
== foldr eats (human `eats` (shark `eats` (fish)) (algae : [])
== foldr eats (human `eats` (shark `eats` (fish `eats` algae))) []
== (human `eats` (shark `eats` (fish `eats` algae)
其语义foldr是：一个人吃了一条已经吃过一条鱼的鲨鱼，而这条鱼已经吃了一些藻类。食物是蓄能器。
两者都foldl从左到右foldr“剥离”食客，所以这不是我们将 foldl 称为“左折叠”的原因。相反，评估的顺序很重要。
于 2012-08-09T20:12:09.210 回答
26
想想foldr的定义:
-- if the list is empty, the result is the initial value z
foldr f z [] = z
-- if not, apply f to the first element and the result of folding the rest
foldr f z (x:xs) = f x (foldr f z xs)
因此例如foldr (-) 54 [10,11]must equal (-) 10 (foldr (-) 54 [11])，即再次扩展 equal (-) 10 ((-) 11 54)。所以内运算为11 - 54，即-43；并且外部操作是10 - (-43)，即10 + 43，因此53正如您所观察到的。对您的第二种情况执行类似的步骤，您将再次看到结果如何形成！
于 2009-11-18T17:46:25.493 回答
22
foldr表示从右边折叠，所以foldr (-) 0 [1, 2, 3]产生(1 - (2 - (3 - 0))). 相比之下foldl产生(((0 - 1) - 2) - 3).
当算子不可交换 foldl时，foldr会得到不同的结果。
在您的情况下，第一个示例扩展(10 - (11 - 54)) 为 53。
于 2009-11-18T17:40:55.427 回答
10
一个简单的理解方法foldr是：它将每个列表构造函数替换为所提供函数的应用程序。您的第一个示例将转换为：
10 - (11 - 54)
从：
10 : (11 : [])
我从 Haskell Wikibook 中得到的一个很好的建议可能在这里有用：
通常，您应该
foldr在可能是无限的列表或折叠正在构建数据结构foldl'的列表中使用，并且如果列表已知是有限的并且归结为单个值。foldl（没有勾号）应该很少使用。
于 2009-11-19T22:23:30.307 回答
7
我一直认为http://foldr.com是一个有趣的插图。请参阅Lambda the Ultimate帖子。
于 2009-11-18T20:12:45.890 回答
5
仔细阅读和比较这里提供的其他答案应该已经清楚了这一点，但值得注意的是，接受的答案可能对初学者有点误导。正如其他评论者所指出的，在 Haskell 中执行的计算文件夹不是“从列表的右侧开始”；否则，foldr永远无法在无限列表上工作（它在 Haskell 中，在适当的条件下）。
Haskell函数的源代码foldr应该清楚地说明这一点：
foldr k z = go
where
go [] = z
go (y:ys) = y `k` go ys
每个递归计算将最左边的原子列表项与列表尾部的递归计算结合起来，即：
a\[1\] `f` (a[2] `f` (a[3] `f` ... (a[n-1] `f` a[n]) ...))
哪里a[n]是初始累加器。
因为归约是“在 Haskell 中懒惰地”完成的，所以它实际上是从左边开始的。这就是我们所说的“惰性求值”，它是 Haskell 著名的一个显着特征。并且理解 Haskell 的操作很重要foldr；因为，事实上，从左边递归地foldr建立和减少计算，可以短路的二元运算符有机会在适当的情况下减少无限列表。foldr
如果说r("right") 和l("left") in foldrandfoldl指的是右结合性和左结合性，或者将其留在那个地方，或者尝试解释 Haskell 的惰性评价机制。
为了完成您的示例，按照foldr源代码，我们构建了以下表达式：
Prelude> foldr (-) 54 [10, 11]
->
10 - [11 - 54] = 53
然后再次：
foldr (\x y -> (x + y) / 2) 54 [12, 4, 10, 6]
->
(12 + (4 + (10 + (6 + 54) / 2) / 2) / 2) / 2 = 12
于 2020-07-30T16:42:17.953 回答
2
我认为以简单的方式实现 map、foldl 和 foldr 有助于解释它们是如何工作的。工作示例也有助于我们的理解。
myMap f [] = []
myMap f (x:xs) = f x : myMap f xs
myFoldL f i [] = i
myFoldL f i (x:xs) = myFoldL f (f i x) xs
> tail [1,2,3,4] ==> [2,3,4]
> last [1,2,3,4] ==> 4
> head [1,2,3,4] ==> 1
> init [1,2,3,4] ==> [1,2,3]
-- where f is a function,
-- acc is an accumulator which is given initially
-- l is a list.
--
myFoldR' f acc [] = acc
myFoldR' f acc l = myFoldR' f (f acc (last l)) (init l)
myFoldR f z [] = z
myFoldR f z (x:xs) = f x (myFoldR f z xs)
> map (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0]
> myMap (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0]
> foldl (\x y -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125
> myFoldL (\x y -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125
foldl from above: Starting accumulator = 54
(12 + 54) / 2 = 33
(4 + 33) / 2 = 18.5
(10 + 18.5) / 2 = 14.25
(6 + 14.25) / 2 = 10.125`
> foldr (++) "5" ["1", "2", "3", "4"] ==> "12345"
> foldl (++) "5" ["1", "2", "3", "4"] ==> “51234"
> foldr (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12
> myFoldR' (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12
> myFoldR (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12
foldr from above: Starting accumulator = 54
(6 + 54) / 2 = 30
(10 + 30) / 2 = 20
(4 + 20) / 2 = 12
(12 + 12) / 2 = 12
于 2017-05-30T05:44:29.273 回答
1
好的，让我们看一下参数：
- 一个函数（它接受一个列表元素和一个与其返回的值相同类型的值（可能的部分结果））；
- 空列表特殊情况的初始结果规范
- 一个列表;
返回值：
- 一些最终结果
它首先将该函数应用于列表中的最后一个元素和空列表结果。然后它用这个结果和前一个元素重新应用函数，依此类推，直到它需要一些当前结果和列表的第一个元素来返回最终结果。
使用一个函数来“折叠”一个初始结果周围的列表，该函数采用一个元素和一些先前的折叠结果。它对每个元素重复此操作。因此，foldr 从列表的末尾或右侧开始执行此操作。
folr f emptyresult [1,2,3,4]变成
f(1, f(2, f(3, f(4, emptyresult) ) ) ) . 现在只需在评估中跟随括号即可。
需要注意的一件重要事情是，提供的函数f必须将其自己的返回值作为其第二个参数处理，这意味着两者必须具有相同的类型。
资料来源：我的帖子，如果您认为它可能会有所帮助，我会从命令式非咖喱的角度来看待它。
于 2013-04-06T18:48:29.027 回答
0
这个 wiki 页面中的图像可视化了foldr（以及foldl）的想法：
例如， 的结果foldr (-) 0 [1,2,3]是 2。它可以可视化为：
-
/ \
1 -
/ \
2 -
/ \
3 0
即（从下到上）：
1 - ( -1 ) = 2
2 - ( 3 )
3 - 0
因此foldr (\x y -> (x+y)/2) 54 [12, 4, 10, 6]正在通过以下方式计算：
12 `f` (12.0) = 12.0
4 `f` (20.0)
10 `f` (30.0)
6 `f` 54
于 2021-11-04T03:26:11.327 回答