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

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

我用 foldl 重写了一下:

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

(注意，step 函数的参数被正确地反转了。)

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

我尝试像在 天启的回答中那样跟踪函数的执行:

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

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

22329 次浏览
小开

您可以在 Haskell 的文档 给你中看到，foldl 是尾递归的，如果传递一个无限列表，它将永远不会结束，因为它在返回一个值之前对下一个参数调用自己..。

小开

我不知道 Haskell，但是在 Scheme 中，fold-right总是首先作用于列表的最后一个元素。因此，对于循环列表(与无限列表相同) ，is 将不起作用。

我不确定 fold-right是否可以写成尾递归的，但是对于任何循环列表，您都应该得到一个堆栈溢出。fold-left OTOH 通常是通过尾递归实现的，如果不提前终止它，就会陷入无限循环。

小开 
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总是在“外面”或“左边”，所以它首先得到扩展。

小开
最佳答案

folds 的不同之处似乎是经常引起混淆的原因，所以这里有一个更为全面的概述:

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

foldl为:

  • 左联 : f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
  • Tail ursive : 它遍历列表，然后生成值
  • Lazy : 在需要结果之前，不对任何内容进行评估
  • 反向 : foldl (flip (:)) []反转一个列表。

foldr为:

  • 右联想 : f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
  • 递归到参数 : 每次迭代都将 f应用到下一个值，并折叠列表的其余部分。
  • Lazy : 在需要结果之前，不对任何内容进行评估
  • 转发 : foldr (:) []返回一个不变的列表。

这里有一个稍微微妙的地方，有时候会让人犯错: 因为 foldl是 倒过来，所以 f的每个应用程序都被添加到结果的 在外面中; 而且因为它是 懒惰，所以在需要结果之前不会进行任何评估。这意味着，要计算结果的任何部分，Haskell 首先遍历构造嵌套函数应用程序表达式的 整个名单，然后计算 最外面函数，根据需要计算其参数。如果 f总是使用它的第一个参数，这意味着 Haskell 必须一直递归到最里面的项，然后向后计算 f的每个应用程序。

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

实际上，即使从技术上讲 foldl是尾递归的，因为整个结果表达式是在计算任何值之前构建的，即 foldl会导致堆栈溢出！

另一方面，考虑 foldr。它也是惰性的，但是因为它运行 前进，所以 f的每个应用程序都被添加到结果的 在里面中。因此，为了计算结果，Haskell 构造了一个 单身函数应用程序，其第二个参数是折叠列表的其余部分。如果 f的第二个参数(例如数据构造函数)是惰性的，那么结果将是 越来越懒，只有在计算结果中需要它的某些部分时，才会计算折叠的每一步。

因此，我们可以看到为什么 foldr有时可以在无限列表上工作，而 foldl却不能: 前者可以延迟地将无限列表转换为另一个延迟的无限数据结构，而后者必须检查整个列表以生成结果的任何部分。另一方面，具有立即需要两个参数的函数(如 (+))的 foldr与 foldl非常相似(或者说不太相似) ，在计算之前构建一个巨大的表达式。

因此，需要注意的两个重要问题是:

  • foldr可以将一个延迟递归数据结构转换为另一个。
  • 否则，延迟折叠将在大型列表或无限列表上因堆栈溢出而崩溃。

你可能已经注意到，听起来 foldr可以做到 foldl所能做的一切，甚至更多。这是真的！事实上，是 折叠几乎是无用的！

但是，如果我们想通过折叠一个大的(但不是无限的)列表来产生一个非惰性结果，该怎么办呢？为此，我们需要一个 严格的折叠，它是 标准图书馆深思熟虑地提供:

foldl'为:

  • 左联 : f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
  • Tail ursive : 它遍历列表，然后生成值
  • 严格 : 沿途评估每个函数应用程序
  • 反向 : foldl' (flip (:)) []反转一个列表。

因为 foldl'是 严格，所以 Haskell 将在每一步计算结果 评估 f，而不是让左参数累积一个巨大的、未求值的表达式。这给了我们通常需要的高效的尾部递归！换句话说:

  • foldl'可以有效地折叠大型列表。
  • foldl'将挂起在无限列表的无限循环中(不会导致堆栈溢出)。

Haskell 维基也有 讨论这件事的一页纸。


提交答案