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

Question

此问题中 myAny函数的代码使用foldr.当谓词满足时,它会停止处理无限列表.

我用foldl重写了它:

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

(请注意,步骤函数的参数已正确反转.)

但是,它不再停止处理无限列表.

我试图在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

但是,这不是函数的行为方式.这怎么了？

Answer 1

如何fold区别似乎经常引起混淆,所以这里有一个更概括的概述:

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

foldl 是:

• 左联想:f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• 尾递归:它遍历列表,然后产生值
• 懒惰:在需要结果之前不评估任何内容
• 向后:foldl (flip (:)) []反转列表.

foldr 是:

• 右联想:f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
• 递归到参数:每次迭代都应用于f下一个值和折叠列表其余部分的结果.
• 懒惰:在需要结果之前不评估任何内容
• 前锋:foldr (:) []返回一个未更改的列表.

这里有多达有时候会绊倒人稍微含蓄一点:由于foldl是向后的每个应用程序f被添加到外界的结果; 因为它是懒惰的,所以在需要结果之前不会对任何内容进行评估.这意味着要计算结果的任何部分,Haskell首先遍历构建嵌套函数应用程序表达式的整个列表,然后评估最外层函数,根据需要评估其参数.如果f总是使用它的第一个参数,这意味着Haskell必须一直递归到最里面的术语,然后向后计算每个应用程序f.

这显然与大多数功能程序员所熟悉和喜爱的高效尾递归相差甚远!

实际上,即使foldl技术上是尾递归,因为整个结果表达式是在评估任何内容之前构建的,foldl可能会导致堆栈溢出!

另一方面,考虑一下foldr.它也是懒惰的,但因为它向前运行,所以每个应用程序都f被添加到结果的内部.因此,为了计算结果,Haskell构造了一个单独的函数应用程序,其第二个参数是折叠列表的其余部分.如果f在其第二个参数(例如数据构造函数)中是惰性的,则结果将是递增延迟的,折叠的每个步骤仅在计算需要它的结果的某些部分时计算.

所以我们可以看到为什么foldr有时在无限列表上工作时foldl:前者可以懒惰地将无限列表转换为另一个惰性无限数据结构,而后者必须检查整个列表以生成结果的任何部分.另一方面,foldr使用一个需要两个参数的函数,例如(+),工作(或者更确切地说,不工作)foldl,在评估它之前构建一个巨大的表达式.

所以需要注意的两点是:

• foldr 可以将一个惰性递归数据结构转换为另一个.
• 否则,在大型或无限列表上堆栈溢出时,惰性折叠将崩溃.

您可能已经注意到它听起来foldr可以做所有事情foldl,还有更多.这是真的!事实上,foldl几乎没用!

但是如果我们想通过折叠大(但不是无限)列表来产生非惰性结果呢？为此,我们需要严格的折叠,标准库可以提供:

foldl' 是:

• 左联想:f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• 尾递归:它遍历列表,然后产生值
• 严格:在此过程中评估每个功能应用程序
• 向后:foldl' (flip (:)) []反转列表.

因为foldl'是严格的,计算结果Haskell将在每一步评估 f,而不是让左参数累积一个巨大的,未评估的表达式.这给了我们想要的通常,有效的尾递归!换一种说法:

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

Haskell wiki也有一个讨论这个问题的页面.

Answer 2

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总是在"外部"或"左",所以它首先被扩展.广告无限.

Answer 3

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