文件夹如何工作？

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

从这里你可以看到列表元素（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 也可以处理无限列表，但我认为最好先了解有限情况。

Answer 3

它有助于理解 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称为“左折叠”的原因。相反，评估的顺序很重要。

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)

from:

10 : (11 : [])

我从 Haskell Wikibook 得到的一个很好的建议在这里可能有一些用处：

作为一项规则，您应该在可能无限或折叠正在构建数据结构的列表上使用 foldr ，如果列表已知，则应使用 foldl'是有限的并且归结为单个值。 foldl（不带勾）应该很少使用。

Answer 7

我一直认为 http://foldr.com 是一个有趣的插图。请参阅 Lambda Ultimate 帖子。

Answer 8

仔细阅读此处提供的其他答案并对其进行比较应该已经清楚了这一点，但值得注意的是，所接受的答案可能会对初学者有点误导。正如其他评论者所指出的，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。

对于初学者来说，说 foldr 中的 r（“右”）和 l（“左”）会减少很多混乱。和 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 9

我认为以简单的方式实现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

Answer 10

好的，让我们看看参数：

• 一个函数（它接受一个列表元素和一个与它返回的值相同类型的值（可能的部分结果））；
• 的初始结果的规范
• 空列表特殊情况列表

；返回值：

• 一些最终结果

它首先将函数应用于列表中的最后一个元素和空列表结果。然后，它使用此结果和前一个元素重新应用该函数，依此类推，直到它使用某个当前结果和列表的第一个元素来返回最终结果。

Fold 使用接受元素和一些先前折叠结果的函数围绕初始结果“折叠”列表。它对每个元素重复此操作。因此，foldr 从列表的末尾或列表的右侧开始执行此操作。

folr femptyresult [1,2,3,4] 变成
f(1, f(2, f(3, f(4, 空结果) ) ) )。现在只需在评估中遵循括号即可。

需要注意的一件重要事情是，提供的函数 f 必须将其自己的返回值作为第二个参数处理，这意味着两者必须具有相同的类型。

资料来源：我的帖子，我从如果您认为它可能有帮助，请使用命令式非柯里化 javascript 观点。

Answer 11

此 wiki 页面中的图像可视化了 foldr（以及 foldl）的概念：

• https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29

例如，foldr (-) 0 的结果[1,2,3] 是 2，可以形象化为：

  -
 / \
1   -
   / \
  2   -
     / \
    3   0

即（从下到上）：

1 - ( -1 )      = 2
    2 - ( 3 )
        3 - 0

所以 foldr (\xy -> (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