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

Question

似乎foldr与列表理解有某种融合,因此与(21mb)相比,它需要更少的内存(11mb)分配foldl,例如

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

有谁可以解释如何以及为什么？另外,懒惰的评价如何帮助.

Answer 1

从本质上讲,我们可以理解这种理解map f xs.如果你正在编译这个,那么ghc应该能够将总和,折叠和地图融合成一个通道:http://www.haskell.org/haskellwiki/Correctness_of_short_cut_fusion.但即使你不是,懒惰也是你的内存使用的朋友.地图生成的列表是懒惰的 - f仅在需要时应用.只有当折叠者要求它时才需要f.而且由于你的折叠器显然正在产生另一个(懒惰)列表,所以折叠的每一步都只需要依次求和.因此,您仍然可以依次应用每个函数,但不需要同时生成完整的中间数据结构.虽然你已经编写了一整套函数组合,但评估模型将倾向于处理这组特定的代码,模拟一大堆挥手,有点像一个循环(尽管没有融合,有一个相当数量的循环)间接).

Answer 2

左侧折叠在遍历整个列表之前不能产生任何输出(结果的一部分).根据您折叠的功能,可以构建一个大数据结构或一个大thunk,它使用大量内存(如果你在列表中折叠例如(+),它可以在常量内存中运行Int).

右侧折叠可以,对于适当的函数(这样可以产生[部分]结果而不检查第二个参数)递增地产生它们的结果,这样如果结果被适当地消耗并且输入列表被适当地生成,则整个计算可以运行在小的恒定空间.正如sclv所说,在这些情况下,它基本上会减少到一个循环.