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实现的,如果不尽早终止的话,它将会陷入无限循环。