7

页面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在下面的评论中建议的那样）

4

1 回答 1

3

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

于 2012-06-19T05:24:04.913 回答