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

怎么用? fold S difference似乎是一种常见的混淆源,因此这里有一个更一般的概述:

考虑折叠n个值的列表 [x1, x2, x3, x4 ... xn ] 有一些功能 f 种子 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 (:) [] 返回一个未更改的列表。

这里有一个微妙的点有时会让人感到困惑:因为 福德尔 是 向后的 每种应用 f 被添加到 外部 结果;因为它是 懒惰的 ,在需要结果之前不计算任何内容。这意味着要计算结果的任何部分,haskell首先迭代 完整列表 构造嵌套函数应用程序的表达式,然后计算 最外面的 函数,根据需要评估其参数。如果 f 总是使用它的第一个参数,这意味着haskell必须一直递归到最里面的项,然后向后计算 f .

这显然与大多数功能程序员所知道和喜爱的高效尾部递归大不相同!

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

另一方面,考虑 福尔德尔 . 它也很懒,但因为它能跑 前锋 ,每次应用 f 被添加到 里面 结果。因此,为了计算结果,haskell构造了一个 单一的 函数应用程序,第二个参数是折叠列表的其余部分。如果 f 在其第二个参数(例如,数据构造函数)中是懒惰的,结果将是 逐渐变懒 ,只有在对需要折叠的结果的某些部分进行评估时才会计算折叠的每个步骤。

所以我们可以知道为什么 福尔德尔 有时在无限列表上工作 福德尔 不:前者可以将一个无限列表惰性地转换成另一个惰性的无限数据结构,而后者必须检查整个列表以生成结果的任何部分。另一方面, 福尔德尔 具有一个立即需要这两个参数的函数,例如 (+) ,工作(或者更确切地说,不工作)很像 福德尔 ,在评估前构建一个巨大的表达式。

所以需要注意的两点是:

• 福尔德尔 可以将一个延迟的递归数据结构转换为另一个。
• 否则,惰性折叠将崩溃,并导致大列表或无限列表上的堆栈溢出。

你可能注意到这听起来像 福尔德尔 什么都能做 福德尔 可以,还有更多。这是真的!事实上, foldl几乎没用!

但是,如果我们想通过折叠一个大的(但不是无限的)列表来产生一个非懒惰的结果呢?为此,我们需要 严格褶皱 哪一个 the standard libraries thoughfully provide :

foldl' 是:

• 左关联 : f(…)(F(F(F(F Z x1)x2)x3)x4)…)xn
• 尾部递归 :它遍历列表,然后生成值
• 严格的 :对每个函数应用程序进行评估。
• 向后的 : foldl' (flip (:)) [] 反转列表。

因为 福德尔 是 严格的 ,计算结果时,Haskell将 评价 f 在每一步中,不要让左参数累积一个巨大的、未计算的表达式。这给了我们通常的,高效的尾部递归我们想要!换言之:

• 福德尔 可以有效折叠大列表。
• 福德尔 将在无限列表上挂起无限循环(不会导致堆栈溢出)。

haskell wiki有 a page discussing this 也一样。

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的文档中看到 here 该foldl是尾部递归的,如果传递一个无限列表,它将永远不会结束,因为它在返回值之前调用下一个参数本身…

我不认识哈斯克尔,但在计划中, fold-right 总是先对列表的最后一个元素执行。因此,IS不适用于循环列表(与无限列表相同)。

我不确定是否 右折叠 可以以递归方式编写尾部,但对于任何循环列表,都应该获得堆栈溢出。 fold-left Otoh通常是用尾递归实现的,如果不尽早终止它,它将陷入无限循环中。