foldl与foldr行为与无限列表
这个问题中 myAny函数的代码使用了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
但是，这不是函数的行为方式。 这是怎么回事？
如何fold似乎是一个混乱的频繁的来源，所以这里是一个更一般的概述：
考虑用一些函数f和种子z折叠n个值[x1, x2, x3, x4 ... xn ]的列表。
foldl是：
- 左联合 ：
f ( ... (f (f (f (fz x1) x2) x3) x4) ...) xn - 尾recursion ：它遍历列表，然后生成值
- 懒惰 ：没有评估，直到需要的结果
- 向后 ：
foldl (flip (:)) []反转列表。
foldr是：
- 右联合 ：
f x1 (f x2 (f x3 (f x4 ... (f xn z) ... ))) - recursion到参数中 ：每次迭代将
f到下一个值，并将折叠列表的其余部分的结果。 - 懒惰 ：没有评估，直到需要的结果
- 前锋 ：
foldr (:) []返回一个不变的列表。
这里有一点微妙的一点，有时候foldl人们往上走：因为foldl是向后的 ，所以f每个应用都被添加到结果的外面 ; 而且因为它是懒惰的 ，直到结果被要求时才评估。 这意味着要计算结果的任何部分，Haskell首先遍历整个列表，构造嵌套的函数应用程序的expression式，然后评估最外层的函数，根据需要评估其参数。 如果f始终使用它的第一个参数，那么这意味着Haskell必须一直递减到最内层的项，然后向后计算f每个应用程序。
这显然与大多数函数式程序员所知道和喜欢的高效的尾recursion相去甚远！
事实上，即使foldl在技术上是尾recursion的，因为整个结果expression式在评估之前就被构build， foldl会导致堆栈溢出！
另一方面，考虑foldr 。 这也是懒惰的，但是因为它向前运行， f每个应用程序都被添加到结果的内部 。 所以，为了计算结果，Haskell构造了一个函数应用程序，其中第二个参数是折叠列表的其余部分。 如果f在第二个参数（例如数据构造f是懒惰的，则结果将是渐进式的 ，只有在计算需要它的结果的某些部分时才计算折叠的每一步。
所以我们可以看到为什么foldr有时会在无限列表上工作： foldl不能：前者可以懒惰地将无限列表转换为另一个懒惰的无限数据结构，而后者必须检查整个列表以生成结果的任何部分。 另一方面，使用一个需要两个参数的函数(+)比如(+) foldr就像foldl一样工作（或者说，不工作），在评估它之前构build一个巨大的expression式。
所以要注意的两点是：
-
foldr可以将一个懒惰的recursion数据结构转换成另一个。 - 否则，懒惰的折叠将在大型或无限列表上发生堆栈溢出。
你可能已经注意到，这听起来像foldr可以做所有foldl可以，再加上。 这是真的！ 事实上， foldl几乎是无用的！
但是如果我们想通过折叠一个大的（但不是无限的）列表来产生一个非惰性的结果呢？ 为此，我们需要一个严格 的标准库 ，它提供了 ：
foldl'是：
- 左联合 ：
f ( ... (f (f (f (fz x1) x2) x3) x4) ...) xn - 尾recursion ：它遍历列表，然后生成值
- 严格 ：每个function应用程序都在评估中
- 向后 ：
foldl' (flip (:)) []反转列表。
因为foldl'是严格的 ，为了计算结果，Haskell将在每一步评估 f ，而不是让左边的参数积累一个巨大的，未评估的expression式。 这给了我们通常的，高效的我们想要的尾recursion！ 换一种说法：
-
foldl'可以高效地折叠大型列表。 -
foldl'会在一个无限循环中挂起（不会导致堆栈溢出）。
Haskell wiki也有一个页面讨论这个问题 。
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总是在“外部”或“左”，所以它首先被扩展。 无限广告。
你可以在Haskell的文档中看到foldl是尾recursion的，如果传递一个无限列表，它将永远不会结束，因为它在返回一个值之前在下一个参数上调用它自己。
我不知道Haskell，但是在Scheme中， fold-right将首先在列表的最后一个元素上“动作”。 因此对于循环列表（这与无限列表相同）将不起作用。
我不确定fold-right可以写成tail-recursive，但是对于任何循环列表，你应该得到一个堆栈溢出。 fold-left OTOH通常是用尾recursion实现的，如果不尽早终止的话，它将会陷入无限循环。
