Haskell:一个更严格的折叠'与​​deepseq

Question

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函数只评估最顶层的构造函数.如果累加器是一个更复杂的对象,那么fold'仍然会建立未评估的thunk.

显而易见的解决办法是改变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在下面的评论中所说)

Answer 1

事实上，您的两个实现foldl有很大不同。不保证需要f z x完全遍历才能x计算出其答案，因此deepseq x (f z x)可能会做不必要的工作；而且，即使x完全评估，也不能保证f z x没有嵌套的重击，因此let z' = deepseq x (f z x) in seq z' (foo z')可能没有做足够的工作。

您所说的问题的正确解决方案是使用foldl'严格的数据类型作为累加器类型；这样，seq只需检查构造函数即可知道整个结构已完全求值，反之强制构造函数将强制整个结构已完全求值。