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

Question

此问题中 myAny函数的代码使用文件夹。当满足谓词时，它将停止处理无限列表。我用foldl重写了它：myAny :: (a -> Bool) -> [a] -> BoolmyAny 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..]) 1even 1 || (foldl step False [2..])False  || (foldl step False [2..])foldl step False [2..]step (foldl step False [3..]) 2even 2 || (foldl step False [3..])True   || (foldl step False [3..])True但是，这不是函数的行为方式。这怎么了

Answer 1

如何fold小号的不同似乎是混乱的常见来源，所以这里的一个更一般的概述：

考虑[x1, x2, x3, x4 ... xn ]使用某些函数f和seed 折叠n个值的列表z。

foldl 是：

左联想：f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn

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

惰性：需要结果之前，不会评估任何内容

向后：foldl (flip (:)) []反转列表。

foldr 是：

右联想：f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))

递归到参数中：每次迭代都适用f于下一个值以及折叠其余列表的结果。

惰性：需要结果之前，不会评估任何内容

转发：foldr (:) []返回不变的列表。

有一个稍微含蓄点在这里，游人们有时高达：由于foldl是向后的每个应用程序f被添加到外界的结果; 并且由于它是惰性的，因此在需要结果之前不会进行任何评估。这意味着，要计算结果的任何部分，Haskell首先遍历整个列表，以构建嵌套函数应用程序的表达式，然后评估最外部的函数，并根据需要评估其参数。如果f始终使用第一个参数，则意味着Haskell必须一直递归到最内层术语，然后向后计算的每个应用程序f。

这显然与大多数函数程序员所知道并喜欢的高效尾递归相去甚远！

实际上，即使foldl从技术上讲，它是尾递归的，但由于整个结果表达式是在求值之前构建的，因此foldl可能导致堆栈溢出！

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

因此，我们可以看到为什么foldr有时在foldl不行的情况下无法工作的原因：前者可以将一个无限列表懒惰地转换为另一个懒惰的无限数据结构，而后者必须检查整个列表以生成结果的任何部分。另一方面，foldr对于立即需要两个参数的函数，例如(+)，可以像一样工作（或更确切地说，不起作用），类似于foldl在评估它之前构建一个巨大的表达式。

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

foldr 可以将一种惰性递归数据结构转换为另一种。

否则，懒惰折叠将在大型或无限列表上崩溃并导致堆栈溢出。

您可能已经注意到，听起来foldr一切foldl都可以做，还有更多。这是真的！实际上，foldl几乎没有用！

但是，如果我们想通过折叠很大（但不是无限）的列表来产生非惰性结果呢？为此，我们需要一个严格的fold，这是标准库提供的：

foldl' 是：

左联想：f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn

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

严格：每个功能应用程序都将一路评估

向后：foldl' (flip (:)) []反转列表。

因为foldl'是strict，为了计算结果，Haskell将在每一步求值 f，而不是让左参数积累一个巨大的，未求值的表达式。这为我们提供了我们想要的通常有效的尾部递归！换一种说法：

foldl' 可以有效地折叠大列表。

foldl' 将挂在无限列表上的无限循环中（不会导致堆栈溢出）。

Haskell Wiki上也有讨论此内容的页面。

Answer 2

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它总是在“外部”或“左侧”，因此它首先被扩展。广告无限。

Answer 3

您可以Haskell的文档中看到这里是与foldl是尾递归，如果传入一个无限列表，因为它返回一个值之前称自己的下一个参数将永远不会结束......