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'产生恒定大小结果的仅使用恒定空间。

然而，这并不一定有效，正如这里所指出的:

The involved seq function does only evaluate the top-most constructor. If the accumulator is a more complex object, then fold' will still build up unevaluated thunks.

显而易见的解决方案是更改 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 中建议的那样)

Answer 1

实际上，您的 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只需要检查构造函数就知道整个结构被完全评估了，反之强制构造函数将强制整个结构被完全评估。