haskell - Haskell : A stricter fold' with deepseq

页面Foldr Foldl Foldl'讨论foldl'，并将其定义为:

foldl' f z []     = z
foldl' f z (x:xs) = let z' = z `f` x
                    in seq z' $ foldl' f z' xs

这样做是为了避免空间泄漏，即产生恒定大小结果的fold'仅使用恒定空间。

但是，这不一定奏效，如下所示:



显而易见的解决方案是如图所示将seq更改为 deepseq (假设您正在使用 NFData ):

foldl_strict f z []     = z
foldl_strict f z (x:xs) = let z' = z `f` x
                          in deepseq z' $ foldl_strict f z' xs

但是我感觉这可能是非常低效的，因为整个循环都需要通过deepseq遍历整个结构(除非编译器可以静态证明这是没有必要的)。

然后我尝试了这个:

foldl_stricter  f z l      = deepseq z $ foldl_stricter' f z l
foldl_stricter' f z []     = z
foldl_stricter' f z (x:xs) = let z' = deepseq x $ z `f` x
                             in seq z' $ foldl_stricter' f z' xs

但是发现有这个问题。以下内容应返回3时失败。

foldl_stricter (\x y -> x + head y) 0 [[1..],[2..]]

所以fold_stricter太严格了。列表不必严格，防止空间泄漏的重要因素是蓄能器严格。 fold_stricter太远，也使列表严格，导致上述操作失败。

这使我们回到fold_strict。在大小为deepseq的数据结构上重复运行n是否会花费O(n)时间，或者仅在第一次使用O(n)时间，之后才使用O(1)？ (正如dbaupp在下面的comment中建议的那样)

最佳答案

实际上，您的foldl的两种实现有很大不同。无法保证f z x将需要完全遍历x来计算其答案，因此deepseq x (f z x)可能会做不必要的工作；此外，即使对x进行了完全评估，也无法保证f z x没有嵌套的thunk，因此let z' = deepseq x (f z x) in seq z' (foo z')可能做不到足够的工作。

正确的解决方法是使用foldl'和严格的数据类型作为累加器类型。这样，seq将只需要检查构造函数就可以知道整个结构都已被完全评估，反之，强制构造函数将强制整个结构将被完全评估。