似乎foldr与列表理解进行了某种融合，因此与foldl此示例中的（21mb）相比，它需要更少的内存（11mb）分配
myfunc = sum $ foldr g acc [ f x | x <- xs ]
f x = ..
g x y = ..
谁能解释一下如何以及为什么？懒惰的评估在这方面也有帮助。
问问题
365 次
3 回答
8
本质上，我们可以将理解脱糖为map f xs. 如果您正在编译它，那么 ghc 确实应该能够将总和、折叠和地图融合到一个通道中：http ://www.haskell.org/haskellwiki/Correctness_of_short_cut_fusion. 但即使你不是，那么懒惰也是你使用内存的朋友。map 生成的列表是惰性的—— f 仅在需要时应用。并且 f 只有当 foldr 需要它时才会被请求。并且由于您的 foldr 显然正在生成另一个（惰性）列表，因此折叠的每一步仅由 sum 依次要求。因此，您仍然可以依次应用每个函数，但您不需要一次生成完整的中间数据结构。当您编写了一组完整的函数组合时，评估模型将倾向于处理这组特定的代码，以一大堆挥手为模，有点像一个循环（尽管没有融合，一个相当数量的循环间接的）。
于 2011-12-09T17:19:59.477 回答
8
在遍历整个列表之前，左折叠不能产生任何输出（结果的一部分）。根据您折叠的功能，它可以构建一个大数据结构或一个大 thunk，它使用大量内存（如果您将例如 (+) 折叠在 列表上，它可以在恒定内存中运行Int）。
对于适当的函数（这样可以在不检查第二个参数的情况下产生[部分]结果），正确的折叠可以增量地产生它们的结果，这样如果结果被适当地消耗并且输入列表被适当地生成，整个计算就可以运行在小的常数空间中。正如 sclv 所说，在这些情况下，它基本上简化为一个循环。
于 2011-12-09T17:24:43.310 回答
1
这是 GHC 编译器的一个特性。基本上，GHC 可以识别何时在“管道”中使用列表，并且可以将整个构造转换为whileC 中完全不分配列表的 -loop 的等价物。
这适用于foldr而不是foldl取决于g您在示例中使用的功能的原因。因为foldr，而不是foldl，累积作为参数给出的函数的结果foldl（又名：在开始实际评估函数之前需要整个列表g，因此它建立了一个巨大的未评估函数“thunk”和list 作为它的结果——这就是为什么它在这种情况下使用更多内存的原因——虽然它foldr可以在获得任何列表输入后立即开始评估g），它在其累加器中被称为“严格”，并且可以做出某些假设可以导致优化的编译器。
例如，如果函数g产生一个列表值，它可以继续前面提到的“管道”优化策略，基本上处理foldr类似 amap并将整个构造（从列表生成到列表消耗）变成一个严格的循环。这仅是可能的，因为foldr它消耗的每个列表元素都会产生一个列表元素，这foldl不能保证这样做（尤其是对于无限列表）。
于 2011-12-09T17:23:26.943 回答