为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

慕容森 2020-02-04 15:27:33
此问题中 myAny函数的代码使用文件夹。当满足谓词时,它将停止处理无限列表。我用foldl重写了它:myAny :: (a -> Bool) -> [a] -> BoolmyAny 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..]) 1even 1 || (foldl step False [2..])False  || (foldl step False [2..])foldl step False [2..]step (foldl step False [3..]) 2even 2 || (foldl step False [3..])True   || (foldl step False [3..])True但是,这不是函数的行为方式。这怎么了
查看完整描述

3 回答

?
富国沪深

TA贡献1790条经验 获得超9个赞

如何fold小号的不同似乎是混乱的常见来源,所以这里的一个更一般的概述:


考虑[x1, x2, x3, x4 ... xn ]使用某些函数f和seed 折叠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构造了一个函数应用程序,其第二个参数是折叠列表的其余部分。如果if f在其第二个参数(例如,数据构造函数)中是lazy,则结果将是lazy递增的,仅当需要评估结果的某些部分时才计算折叠的每一步。


因此,我们可以看到为什么foldr有时在foldl不行的情况下无法工作的原因:前者可以将一个无限列表懒惰地转换为另一个懒惰的无限数据结构,而后者必须检查整个列表以生成结果的任何部分。另一方面,foldr对于立即需要两个参数的函数,例如(+),可以像一样工作(或更确切地说,不起作用),类似于foldl在评估它之前构建一个巨大的表达式。


因此,需要注意的两个重要点是:


foldr 可以将一种惰性递归数据结构转换为另一种。

否则,懒惰折叠将在大型或无限列表上崩溃并导致堆栈溢出。

您可能已经注意到,听起来foldr一切foldl都可以做,还有更多。这是真的!实际上,foldl几乎没有用!


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


foldl' 是:

左联想:f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn

尾递归:遍历列表,然后产生值

严格:每个功能应用程序都将一路评估

向后:foldl' (flip (:)) []反转列表。

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


foldl' 可以有效地折叠大列表。

foldl' 将挂在无限列表上的无限循环中(不会导致堆栈溢出)。

Haskell Wiki上也有讨论此内容的页面。


查看完整回答
反对 回复 2020-02-04
?
不负相思意

TA贡献1777条经验 获得超10个赞

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它总是在“外部”或“左侧”,因此它首先被扩展。广告无限。


查看完整回答
反对 回复 2020-02-04
?
慕码人2483693

TA贡献1860条经验 获得超9个赞

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


查看完整回答
反对 回复 2020-02-04
  • 3 回答
  • 0 关注
  • 565 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信