列表推导式中是否创建了任何中间数据结构？

Question

看起来foldr与列表理解进行了某种融合，因此在这个例子中，与foldl相比，它需要更少的内存（11mb）分配。

myfunc = sum $ foldr g acc [ f x | x <- xs ]
f x = ..
g x y = ..

有人能解释一下如何以及为什么吗？还有懒惰求值如何帮助解决此问题。

- vis

Answer 1

我们可以将推导式简化为基本的map f xs。如果您正在编译此代码，则ghc确实能够将求和、折叠和映射融合为单个步骤：http://www.haskell.org/haskellwiki/Correctness_of_short_cut_fusion。但即使您没有进行编译，惰性计算也可以帮助您减少内存使用。由map生成的列表是惰性的--只有在需要时才会应用f。而且只有在foldr需要时才会要求f。由于您的foldr明显生成另一个（惰性）列表，因此每个fold的步骤都只由sum依次要求。因此，您仍然需要依次应用每个函数，但不需要立即生成完整的中间数据结构。虽然您编写了一组全面的函数组合，但评估模型往往会将这个特定的代码集与一堆手摇相结合，视为循环（虽然在没有融合的情况下，存在相当多的间接引用）。

- sclv

Answer 2

左折叠在遍历整个列表之前不能产生任何输出（结果的一部分）。根据您折叠的功能，这可能会构建一个大数据结构或大 thunk，这将使用大量内存（如果您在Int列表上折叠例如 (+)，则可以在恒定内存中运行）。

对于适当的函数（可以在不检查第二个参数的情况下产生[部分]结果），右折叠可以逐步生成它们的结果，因此如果结果得到适当消耗并且输入列表适当生成，则整个计算可以在小的恒定空间中运行。正如sclv所说，在这些情况下，它基本上缩减为一个循环。

- Daniel Fischer

---

谢谢。我选择这个答案是因为它清晰地区分了foldr和foldl。 - vis

Answer 3

这是 GHC 编译器的一个特性。基本上，GHC 可以识别列表在“管道”中使用时，并将整个结构转换为 C 中等价的不分配列表的 while 循环。

这个特性能够与 foldr 一起工作而不是 foldl，取决于你在示例中使用的函数 g。由于 foldr 累积给定参数的函数的结果（也就是说，foldl 需要整个列表才能开始实际评估函数 g，因此它会建立一个巨大的未评估函数和列表中的最后一个元素作为其结果 - 这就是为什么在这种情况下它使用了更多的内存 - 而 foldr 可以在获得任何列表输入后立即开始评估 g），因此它在累加器中被称为“严格”，编译器可以做出某些假设，从而导致优化。

如果函数 g 返回的是一个列表，那么它可以继续前面提到的“管道”优化策略，基本上将 foldr 当作 map 来处理，并将整个结构（从列表生成到列表消耗）变成一个严格的循环。这只有在 foldr 对于每个它消耗的列表元素都产生了恰好一个列表元素时才可能实现，而 foldl 并不能保证这样做（特别是对于无限列表）。

- dflemstr

---

这并不是 GHC 的一个特性，准确来说，GHC 支持任何库的重写规则——不仅仅是列表——而 fold/build 融合就是基于此实现的。 - Louis Wasserman