list - 向左和向右折叠无限列表

Question

我对 Learn You A Haskell 中的以下段落有疑问(我认为是一本好书，不是鄙视它):

One big difference is that right folds work on infinite lists, whereas left ones don't! To put it plainly, if you take an infinite list at some point and you fold it up from the right, you'll eventually reach the beginning of the list. However, if you take an infinite list at a point and you try to fold it up from the left, you'll never reach an end!

我就是不明白这一点。如果你拿一个无限列表并尝试从右侧折叠它，那么你必须从无穷大点开始，但这种情况不会发生(如果有人知道可以执行此操作的语言，请告诉:p )。至少，您必须根据 Haskell 的实现从那里开始，因为在 Haskell 中，foldr 和 Foldl 不采用参数来确定它们应该在列表中的何处开始折叠。

我同意引用，当且仅当foldr和foldl采用参数来确定它们应该在列表中的何处开始折叠时，因为如果您采用无限列表并从定义的索引开始折叠，那么它会 最终终止，而从左折叠开始的位置并不重要；你将向无穷大折叠。然而，foldr 和foldl 不接受这个论点，因此引用没有意义。在 Haskell 中，无限列表上的左折叠和右折叠都不会终止。

我的理解正确还是我遗漏了什么？

Answer 1

这里的关键是懒惰。如果您用于折叠列表的函数是严格的，那么给定无限列表，左折叠和右折叠都不会终止。

Prelude> foldr (+) 0 [1..]
^CInterrupted.

但是，如果您尝试折叠不太严格的函数，则可能会得到终止结果。

Prelude> foldr (\x y -> x) 0 [1..]
1

您甚至可以获得一个无限数据结构的结果，因此虽然它在某种意义上不会终止，但它仍然能够生成可以延迟使用的结果。

Prelude> take 10 $ foldr (:) [] [1..]
[1,2,3,4,5,6,7,8,9,10]

但是，这不适用于 foldl，因为无论是否惰性，您都永远无法计算最外层的函数调用。

Prelude> foldl (flip (:)) [] [1..]
^CInterrupted.
Prelude> foldl (\x y -> y) 0 [1..]
^CInterrupted.

请注意，左折叠和右折叠之间的主要区别不是遍历列表的顺序(始终从左到右)，而是结果函数应用程序的嵌套方式。

• 使用foldr，它们嵌套在“内部”

  foldr f y (x:xs) = f x (foldr f y xs)
  

  这里，第一次迭代将导致f的最外层应用。因此，f 有机会变得懒惰，这样第二个参数要么不总是被求值，要么它可以生成数据结构的某些部分而不强制其第二个参数。

• 使用foldl，它们嵌套在“外部”

  foldl f y (x:xs) = foldl f (f y x) xs
  

  在这里，在到达 f 的最外层应用程序之前，我们无法评估任何内容，在无限列表的情况下，无论 f 是否有效，我们都永远不会到达该应用程序code> 是否严格。