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 foldl (flip (:)) []反转列表。 foldr是：
f x1 (f x2 (f x3 (f x4 ... (f xn z) ... ))) f应用于下一个值以及折叠列表的其余部分的结果。 foldr (:) []返回一个不变的列表。 这里有一点微妙的一点，有时foldl人们往上走：因为foldl是向后的 ，所以f每个应用都会添加到结果的外部; 并且因为它是懒惰的 ，所以只有在结果是必需的时候才进行评估。 这意味着要计算结果的任何部分，Haskell首先遍历整个列表，构造嵌套函数应用程序的表达式，然后评估最外层函数，根据需要评估其参数。 如果f始终使用它的第一个参数，这意味着Haskell必须一直递减到最内层的项，然后向后计算f每个应用程序。
这显然与大多数函数式程序员都知道并喜欢的有效尾递归相去甚远！
事实上，即使foldl在技术上是尾递归的，因为整个结果表达式在评估任何事情之前都会被构建， foldl会导致堆栈溢出！
另一方面，考虑foldr 。 它也很懒，但是因为它向前运行， f每个应用程序都被添加到结果的内部。 因此，为了计算结果，Haskell构造了一个函数应用程序，其中第二个参数是折叠列表的其余部分。 如果f在其第二个参数（数据构造f是懒惰的，则结果将递增地延迟 ，并且仅在需要它的结果的一部分被评估时才计算折叠的每一步。
所以我们可以看到为什么foldr有时会在无限列表上工作： foldl不会：前者可以懒惰地将无限列表转换为另一个懒惰的无限数据结构，而后者必须检查整个列表以生成结果的任何部分。 另一方面，使用一个函数立即需要两个参数的foldr (+)比如(+) ，就像foldl一样工作（或者说，不起作用），在评估它之前构建一个巨大的表达式。
所以需要注意的两点是：
foldr可以将一个懒惰的递归数据结构转换为另一个。 你可能已经注意到，它听起来像foldr可以做所有的foldl可以，再加上更多。 这是真的！ 事实上， foldl几乎是无用的！
但是如果我们想通过折叠一个大的（但不是无限的）列表来产生一个非惰性的结果呢？ 为此，我们需要一个严格的折叠 ，标准库通过提供：
foldl'是：
f ( ... (f (f (f (fz x1) x2) x3) x4) ...) xn foldl' (flip (:)) []反转列表。 因为foldl'是严格的 ，为了计算结果，Haskell将在每一步评估f ，而不是让左边的参数累积一个巨大的，未评估的表达式。 这给了我们我们想要的通常的，高效的尾递归！ 换一种说法：
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是尾递归的，并且如果传递一个无限列表将永远不会结束，因为它在返回值之前在下一个参数上调用它自己...
链接地址: http://www.djcxy.com/p/80723.html