文件夹如何工作？

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开始于列表的右手端，并使用你给它的功能结合了累加器值的每个列表条目。其结果是累加器中的所有列表中的元素“折叠”后的最终值。其类型是：

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 2

要了解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 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)

从：

10 : (11 : [])

有一个好建议，我从哈斯克尔维基教科书有可能是一些使用此：

  

你应该列出了可能是无穷的，在折叠建立一个数据结构，foldr如果列表被称为是有限的，归结为一个单一的值使用foldl'的规则。 foldl（没有蜱）应该很少在所有被使用。

Answer 7

我一直认为 http://foldr.com 是一个有趣的例证。请参阅 LAMBDA终极交

Answer 8

我认为，在一个简单的方式实现的地图，与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 9

好吧，让我们看看论据：

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

返回值：

• 一些最终结果

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

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

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

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

来源： 我的帖子 如果您认为它可能有帮助，我会从命令式非柯里化 JavaScript 角度来看待它。