具有无限列表的foldl 与foldr 行为

发布于 2024-09-06 13:22:48 字数 921 浏览 1 评论 0原文

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

我使用 Foldl 重写了它：（

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

请注意，step 函数的参数已正确反转。）

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

我尝试跟踪函数的执行，如 Apocalisp 的回答：

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

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

原文

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?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

情魔剑神 2024-09-13 13:22:48

fold 的不同之处似乎是常见的混乱来源，因此这里有一个更一般的概述：

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

`foldl` 为：

左关联：f ( ... (f (f (f (fz x1) x2) x3) x4) ...) xn< /code>
尾递归：它迭代列表，然后生成值
惰性：在需要结果之前不会评估任何内容
向后：< code>foldl(flip (:)) [] 反转列表。

`foldr` 是：

右关联：f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
递归到参数：每次迭代将 f 应用于下一个值以及折叠列表其余部分的结果。
惰性：在需要结果之前不会评估任何内容
转发：foldr (:) [] 返回未更改的列表。

这里有一个稍微微妙的点，有时会让人绊倒：因为 foldl 是向后，f 的每个应用都被添加到外部< /em> 结果；并且因为它是惰性的，所以在需要结果之前不会评估任何内容。这意味着要计算结果的任何部分，Haskell 首先迭代整个列表，构建嵌套函数应用程序的表达式，然后计算最外面的函数，将其参数计算为需要。如果f总是使用它的第一个参数，这意味着Haskell必须一直递归到最里面的项，然后向后计算f的每个应用程序。

这显然与大多数函数式程序员所了解和喜爱的高效尾递归相去甚远！

事实上，尽管 foldl 在技术上是尾递归的，但由于整个结果表达式是在计算任何内容之前构建的，foldl 可能会导致堆栈溢出！

另一方面，考虑foldr。它也是惰性的，但由于它向前运行，f 的每个应用都会添加到结果的内部。因此，为了计算结果，Haskell 构造了一个单函数应用程序，其第二个参数是折叠列表的其余部分。如果 f 在其第二个参数（例如数据构造函数）中是惰性的，那么结果将是增量惰性，仅当某些部分时才计算折叠的每个步骤评估需要的结果。

因此，我们可以明白为什么 foldr 有时可以在无限列表上工作，而 foldl 却不能：前者可以将无限列表惰性地转换为另一个惰性无限数据结构，而后者必须检查整个列表以生成结果的任何部分。另一方面，带有立即需要两个参数的函数的 foldr（例如 (+)），其工作方式（或者更确切地说，不起作用）与 非常相似Foldl，在评估之前构建一个巨大的表达式。

因此，需要注意的两个要点是：

foldr 可以将一种惰性递归数据结构转换为另一种。
否则，惰性折叠将因堆栈溢出而崩溃。或无限列表。

您可能已经注意到，听起来 foldr 可以做 foldl 可以做的所有事情，甚至更多。这是真实的！事实上，foldl 几乎没用！

但是，如果我们想通过折叠一个大（但不是无限）列表来产生非惰性结果怎么办？为此，我们需要一个严格折叠，即标准库精心提供了：

`foldl'`是：

左关联：f ( ... ( f (f (f (fz x1) x2) x3) x4) ...) xn
尾递归：它迭代列表，然后生成值
严格：每个函数应用程序都按照向后的方式进行评估
：foldl' (flip (:)) [] 反转列表。

因为 foldl' 是严格，为了计算结果，Haskell 将在每一步评估 f，而不是让左派论证积累了一个巨大的、未经评估的表达。这为我们提供了我们想要的通常的、高效的尾递归！换句话说：

foldl'可以有效地折叠大型列表。
foldl'将挂在无限循环中（不会导致堆栈溢出））在无限列表上。

Haskell wiki 有一个讨论此问题的页面，如出色地。

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.

回复收藏 0 原文

国粹 2024-09-13 13:22:48

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

直观上

，foldl 始终位于“外侧”或“左侧”，因此它首先被展开。无穷无尽。

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

etc.

Intuitively, foldl is always on the "outside" or on the "left" so it gets expanded first. Ad infinitum.

回复收藏 0 原文