foldr如何工作？

Question

任何人都能解释一下如何foldr运作？

拿这些例子:

Prelude> foldr (-) 54 [10, 11]
53
Prelude> foldr (\x y -> (x+y)/2) 54 [12, 4, 10, 6]
12.0

我对这些处决感到困惑.有什么建议？

Answer 1

理解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

Answer 2

foldr从列表的右端开始,使用您提供的函数将每个列表条目与累加器值组合在一起.结果是在所有列表元素中"折叠"之后累加器的最终值.它的类型是:

foldr :: (a -> b -> b) -> b -> [a] -> b

从中您可以看到list元素(类型a)是给定函数的第一个参数,而accumulator(类型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我认为,也可以在无限列表上工作,但最好先了解有限的情况.

Answer 3

它有助于理解之间的区别foldr和foldl.为什么foldr叫"右折"？

最初我认为这是因为它从右到左消耗了元素.不过,两人都foldr和foldl消费清单由左到右.

• foldl 从左到右评估(左关联)
• foldr 从右到左评估(右关联)

我们可以通过使用关联性很重要的运算符的示例来明确区分.我们可以使用人类的例子,比如运营商,"吃":

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为理由"左折".相反,评估的顺序很重要.

Answer 4

考虑一下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]必须相等(-) 10 (foldr (-) 54 [11]),即再次扩张,相等(-) 10 ((-) 11 54).所以内部操作就是11 - 54-43; 和外操作10 - (-43),也就是10 + 43,所以53当你观察.对你的第二个案例进行类似的步骤,你将再次看到结果如何形成!

Answer 5

foldr意味着从右边折叠,所以foldr (-) 0 [1, 2, 3]产生(1 - (2 - (3 - 0))).比较foldl产生(((0 - 1) - 2) - 3).

当运营商不交换 foldl,并foldr会得到不同的结果.

在您的情况下,第一个示例扩展(10 - (11 - 54)) 为53.

Answer 6

一个简单的理解方法foldr是:它用所提供功能的应用程序替换每个列表构造函数.您的第一个示例将转换为:

10 - (11 - 54)

从:

10 : (11 : [])

我从Haskell Wikibook获得的一条很好的建议可能在这里有用:

作为一项规则,您应该使用foldr可能无限的列表或折叠正在构建数据结构foldl'的列表,并且如果已知列表是有限的并且归结为单个值.foldl(根本没有勾选)应该很少使用.

Answer 7

仔细阅读此处提供的其他答案并对其进行比较应该已经清楚了这一点，但值得注意的是，所接受的答案可能会对初学者有点误导。正如其他评论者所指出的，Haskell 中执行的计算foldr 并不是“从列表的右手端开始”；而是“从列表的右端开始”。否则，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对于初学者来说，说 和 中的(“右”) 和l(“左”)foldr指foldl的是右结合性和左结合性，或者就这样，或者尝试解释 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

Answer 8

我一直认为http://foldr.com是一个有趣的例子。参见Lambda Ultimate帖子。