foldl与foldr行为与无限列表 [英] foldl versus foldr behavior with infinite lists

问题描述

中的myAny函数的代码这个问题使用foldr。当谓词满足时停止处理无限列表。

我用foldl重写了它：

  myAny ::（a  - > Bool） - > [a]  - > Bool 
 myAny p list = foldl step False list 
 where 
 step acc item = p item || acc  

（请注意，step函数的参数正确颠倒过来。）

但是，它不再停止处理无限列表。

我尝试跟踪 Apocalisp's answer ：

  myAny即使[1 ..] 
 foldl step False [1 ..] 
 step（foldl step False [2 ..]）1 
甚至1 || （foldl step False [2 ..]）
 False || （foldl step False [2 ..]）
 foldl step False [2 ..] 
 step（foldl step False [3 ..]）2 
 even 2 || （foldl step False [3 ..]）
 True || （foldl step False [3 ..]）
 True  

然而，这不是函数行为的方式。这是怎么回事？

解决方案

如何 fold 一个常见的混淆来源，所以这里有一个更全面的概述：

考虑折叠n个值的列表 [x1，x2，x3，x4。 .. xn] 与一些函数 f 和种子 z 。

foldl 是：

• 左联合： f（...（f（f（f（fz x1）x2）x3）x4）...）xn


• 尾递归：遍历列表，然后生成值


• 懒惰：Nothing is评估直到需要结果


• 向后： foldl（flip（:)）[] 列表。

foldr 是：

• 右联合： f x1（f x2（f x3（f x4 ...（f xn z）..） 。）））


• 递归到参数：每次迭代都会将 f 应用于下一个值以及折叠列表的其余部分。 强>延迟：直到需要结果才进行评估


• 前进： foldr（:) [] code>返回一个列表不变。







这里有一点微妙的一点， c> foldl 是 backwards f 的每个应用程序都添加到外部 结果;并且因为它是懒惰，所以只有在结果是必需的时候才会进行评估。这意味着要计算结果的任何部分，Haskell首先遍历整个列表构造嵌套函数应用程序的表达式，然后评估最外层函数，并将其参数评估为需要。如果 f 总是使用它的第一个参数，这意味着Haskell必须一直递减到最内部的项，然后向后计算每个 f的应用程序。

这显然与大多数功能程序员都知道并喜欢的有效尾递归相去甚远！

实际上，即使 foldl 在技术上是尾递归的，因为整个结果表达式是在评估任何内容之前构建的， <$ c $另一方面，考虑 foldr code>。它也很懒，但是因为它运行 forwards ，所以 f 的每个应用程序都被添加到结果的里面。因此，为了计算结果，Haskell构造了一个单个函数应用程序，其中的第二个参数是折叠列表的其余部分。如果 f 在其第二个参数（例如数据构造函数）中是懒惰的，则结果将是渐进式懒惰，每一步只有当需要它的结果的一部分被评估时才计算。

所以我们可以看到为什么 foldr 有时当 foldl 不会：前者可以懒惰地将无限列表转换为另一个懒惰的无限数据结构，而后者必须检查整个列表以生成任何部分的结果。另一方面， foldr 带有需要立即使用两个参数的函数，如（+），起作用（或相反，它不起作用），就像 foldl ，在评估它之前建立一个巨大的表达式。

重要的要点是：

• foldr 可以转换一个懒惰递归数据结构转换为另一个数据结构。
$ b

您可能已经注意到它听起来像 foldr 可以做所有事情 foldl 可以，再加上更多。这是真的！事实上， foldl几乎是无用的！ 但是如果我们想通过折叠一个大的（但不是无限）列表？为此，我们需要严格折叠，标准库通过提供：

foldl'是：
$ b

• 左结合： f（...（f（f f（fz x1）x2）x3）x4）...）xn


• 尾递归：遍历列表，然后产生值


• 严格：每个函数应用程序都会被评估


• 向后： foldl'（flip（:)）[] 反转列表。
  

<因为 foldl'是 strict ，所以计算结果Haskell会评估 f ，而不是让左边的参数累积一个巨大的，未评估的表达式。这给了我们我们想要的通常的，高效的尾递归！换句话说：

• foldl'可以高效地折叠大型列表。


• foldl'将在一个无限循环中挂起（不会导致堆栈溢出） 。

Haskell wiki有一个讨论这个的页面。

The code for the myAny function in this question uses foldr. It stops processing an infinite list when the predicate is satisfied.

I rewrote it using foldl:

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldl step False list
   where
      step acc item = p item || acc

(Note that the arguments to the step function are correctly reversed.)

However, it no longer stops processing infinite lists.

I attempted to trace the function's execution as in Apocalisp's answer:

myAny even [1..]
foldl step False [1..]
step (foldl step False [2..]) 1
even 1 || (foldl step False [2..])
False  || (foldl step False [2..])
foldl step False [2..]
step (foldl step False [3..]) 2
even 2 || (foldl step False [3..])
True   || (foldl step False [3..])
True

However, this is not the way the function behaves. How is this wrong?

解决方案

How folds differ seems to be a frequent source of confusion, so here's a more general overview:

Consider folding a list of n values [x1, x2, x3, x4 ... xn ] with some function f and seed z.

foldl is:

• Left associative: f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• Tail recursive: It iterates through the list, producing the value afterwards
• Lazy: Nothing is evaluated until the result is needed
• Backwards: foldl (flip (:)) [] reverses a list.

foldr is:

• Right associative: f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
• Recursive into an argument: Each iteration applies f to the next value and the result of folding the rest of the list.
• Lazy: Nothing is evaluated until the result is needed
• Forwards: foldr (:) [] returns a list unchanged.

There's a slightly subtle point here that trips people up sometimes: Because foldl is backwards each application of f is added to the outside of the result; and because it is lazy, nothing is evaluated until the result is required. This means that to compute any part of the result, Haskell first iterates through the entire list constructing an expression of nested function applications, then evaluates the outermost function, evaluating its arguments as needed. If f always uses its first argument, this means Haskell has to recurse all the way down to the innermost term, then work backwards computing each application of f.

This is obviously a far cry from the efficient tail-recursion most functional programmers know and love!

In fact, even though foldl is technically tail-recursive, because the entire result expression is built before evaluating anything, foldl can cause a stack overflow!

On the other hand, consider foldr. It's also lazy, but because it runs forwards, each application of f is added to the inside of the result. So, to compute the result, Haskell constructs a single function application, the second argument of which is the rest of the folded list. If f is lazy in its second argument--a data constructor, for instance--the result will be incrementally lazy, with each step of the fold computed only when some part of the result that needs it is evaluated.

So we can see why foldr sometimes works on infinite lists when foldl doesn't: The former can lazily convert an infinite list into another lazy infinite data structure, whereas the latter must inspect the entire list to generate any part of the result. On the other hand, foldr with a function that needs both arguments immediately, such as (+), works (or rather, doesn't work) much like foldl, building a huge expression before evaluating it.

So the two important points to note are these:

• foldr can transform one lazy recursive data structure into another.
• Otherwise, lazy folds will crash with a stack overflow on large or infinite lists.

You may have noticed that it sounds like foldr can do everything foldl can, plus more. This is true! In fact, foldl is nearly useless!

But what if we want to produce a non-lazy result by folding over a large (but not infinite) list? For this, we want a strict fold, which the standard libraries thoughfully provide:

foldl' is:

• Left associative: f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• Tail recursive: It iterates through the list, producing the value afterwards
• Strict: Each function application is evaluated along the way
• Backwards: foldl' (flip (:)) [] reverses a list.

Because foldl' is strict, to compute the result Haskell will evaluate f at each step, instead of letting the left argument accumulate a huge, unevaluated expression. This gives us the usual, efficient tail recursion we want! In other words:

• foldl' can fold large lists efficiently.
• foldl' will hang in an infinite loop (not cause a stack overflow) on an infinite list.

The Haskell wiki has a page discussing this, as well.

这篇关于foldl与foldr行为与无限列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！