左和右折叠无限列表
我有一个问题，从学习你一个Haskell （伟大的书，不要dising它）以下的段落：
一个很大的区别是，正确的折叠在无限的列表上工作，而左边的不是！ 说白了，如果你在某个时候拿出一个无限的列表，而你从右侧折叠起来，你最终会到达列表的开头。 但是，如果你在一个点上有一个无限的列表，而你试图从左边折叠它，那么你将永远无法达到目的！
我只是不明白这一点。 如果你有一个无限的列表，试着把它从右边折叠起来，那么你将不得不从无穷远处开始，这是不会发生的（如果有人知道你可以做到这一点的语言， ）。 至less，根据Haskell的实现，你必须从Haskell的实现开始，因为在Haskell中，foldr和foldl不会接受一个参数来确定列表中哪些位置应该开始折叠。
我会同意这个引用iff foldr和foldl接受了一个参数来确定列表中他们应该开始折叠的位置，因为如果你从一个已定义的索引中取出一个无限的列表并开始折叠， 它将最终终止，不pipe你从哪里开始， 你会向无穷大折叠。 然而，foldr和foldl 并不认为这个论点，因此这个引用是毫无意义的。 在Haskell中，无限列表中的左alignment和右alignment都不会终止 。
我的理解是正确的还是我错过了什么？
这里的关键是懒惰。 如果你用来折叠列表的函数是严格的，那么给定一个无限列表，那么左边的折叠和右边的折叠都不会终止。
Prelude> foldr (+) 0 [1..] ^CInterrupted.
但是，如果您尝试折叠不太严格的函数，则可以得到终止结果。
Prelude> foldr (\xy -> x) 0 [1..] 1
你甚至可以得到一个无限数据结构的结果，所以尽pipe它在某种意义上不会终止，但它仍然能够产生一个可以被懒惰消耗的结果。
Prelude> take 10 $ foldr (:) [] [1..] [1,2,3,4,5,6,7,8,9,10]
然而，这对foldl不起作用，因为你将永远无法评估最外面的函数调用，懒惰或不。
Prelude> foldl (flip (:)) [] [1..] ^CInterrupted. Prelude> foldl (\xy -> y) 0 [1..] ^CInterrupted.
请注意，左侧和右侧折叠之间的关键区别并不是列表遍历的顺序，它总是从左到右，而是结果函数应用程序如何嵌套。
-
与
foldr，他们嵌套在“内部”foldr fy (x:xs) = fx (foldr fy xs)在这里，第一次迭代将导致
f的最外层应用程序。 因此，f有机会懒惰，所以第二个参数要么不总是被求值，要么就产生一个数据结构的一部分而不强制它的第二个参数。 -
与
foldl，他们嵌套在“外面”foldl fy (x:xs) = foldl f (fxy) xs在这里，我们不能评价任何东西，直到我们已经达到
f的最外层应用程序，在无限列表的情况下我们将永远达不到，而不pipef是否严格。
关键词是“在某个时刻”。
如果你在某个时候拿出一个无限的列表，而你从右侧折叠起来，那么你最终会到达列表的开头。
所以你是对的，你不可能从无限列表的“最后”元素开始。 但作者的观点是：假设你可以。 只要在外面select一个点就可以了（对于工程师来说，这个“足够接近”到无穷大）并开始向左折叠。 最终你会在名单的开始。 左边的折叠也是如此，如果你在那里select一个点（并且把它称为“足够接近”到列表的开头），并且向右折叠，那么你仍然有一个无限的路要走。
所以诀窍是，有时你不需要去无穷大。 你甚至可能不需要去那里。 但是你可能不知道你需要走多远，在这种情况下无限的列表是非常方便的。
简单的例子是foldr (:) [] [1..] 。 让我们来进行折叠。
回想一下， foldr fz (x:xs) = fx (foldr fz xs) 。 在一个无限的列表中，它实际上并不重要，所以我只是把它保留为z而不是[] ，它使图表混乱
foldr (:) z (1:[2..]) ==> (:) 1 (foldr (:) z [2..]) 1 : foldr (:) z (2:[3..]) ==> 1 : (:) 2 (foldr (:) z [3..]) 1 : 2 : foldr (:) z (3:[4..]) ==> 1 : 2 : (:) 3 (foldr (:) z [4..]) 1 : 2 : 3 : ( lazily evaluated thunk - foldr (:) z [4..] )
尽pipe在理论上是右边的一个折叠，但是在这种情况下，究竟是如何从左边开始实际生成列表中的单个元素呢？ 所以如果你从这个列表中take 3 ，你就可以清楚地看到它能够产生[1,2,3] ，而不需要进一步评估折叠。
记住，在Haskell中，你可以使用无限列表，因为懒惰的评估。 所以， head [1..]只是1， head $ map (+1) [1..]是2，尽pipe`[1 ..]是无限长的。 如果你不这样做，停下来玩一会儿。 如果你明白了，请继续阅读…
我认为你的困惑的一部分是， foldl和foldr总是从一边或另一边开始，因此你不需要给出一个长度。
foldr有一个非常简单的定义
foldr _ z [] = z foldr fz (x:xs) = fx $ foldr fz xs
为什么这可能会终止在无限的列表，试试
dumbFunc :: a -> b -> String dumbFunc _ _ = "always returns the same string" testFold = foldr dumbFunc 0 [1..]
这里我们传入一个“”（因为这个值并不重要）和自然数的无限列表。 这是否终止？ 是。
它终止的原因是因为Haskell的评估等同于懒惰的术语重写。
所以
testFold = foldr dumbFunc "" [1..]
变成（允许模式匹配）
testFold = foldr dumbFunc "" (1:[2..])
这是相同的（从我们的折叠定义）
testFold = dumbFunc 1 $ foldr dumbFunc "" [2..]
现在通过dumbFunc的定义我们可以得出结论
testFold = "always returns the same string"
当我们有function做某事，但有时懒惰的时候，这更有趣。 例如
foldr (||) False
用于查找列表是否包含True元素。 我们可以使用这个来定义高阶函数， any返回True函数当且仅当列表的某个元素的传入函数为真
any :: (a -> Bool) -> [a] -> Bool any f = (foldr (||) False) . (map f)
懒惰评估的好处是，当遇到第一个元素e时，这将停止，使得fe == True
另一方面，这不是真的。 为什么？ 那么一个非常简单的foldl看起来像
foldl fz [] = z foldl fz (x:xs) = foldl f (fzx) xs
现在，如果我们尝试了上面的例子，会发生什么
testFold' = foldl dumbFunc "" [1..] testFold' = foldl dumbFunc "" (1:[2..])
现在变成：
testFold' = foldl dumbFunc (dumbFunc "" 1) [2..]
所以
testFold' = foldl dumbFunc (dumbFunc (dumbFunc "" 1) 2) [3..] testFold' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) [4..] testFold' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) 4) [5..]
等等等等。 我们永远无法到达任何地方，因为Haskell总是首先评估最外层的函数（简而言之就是懒惰评估）。
这样做的一个很酷的结果就是你可以用foldr来实现foldl ，反之亦然。 这意味着在一些深刻的方面， foldr是所有高阶string函数中最基本的，因为它是我们用来实现几乎所有其他字符的函数。 有时您可能还想使用foldl ，因为您可以recursion地实现foldl tail，并从中获得一些性能提升。
Haskell wiki上有简单的解释。 它显示了不同types的折叠和累加器function的逐步减less。
你的理解是正确的。 我想知道作者是否试图谈论哈斯克尔的懒惰评估系统（在这个系统中，你可以将一个无限列表传递给不包含折叠的各种函数，而且只会评估返回答案所需的很多东西）。 但是我同意你的观点，作者在这一段里描述的东西不是很好，而且说的是错的。
