哈斯克尔：一个更严格的折叠'与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函数只评估最顶层的构造函数。 如果累加器是一个更复杂的对象，那么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 。 对于大小为n的数据结构，重复运行deepseq是否需要O(n)时间，或者第一次只有O(n)时间，之后是O(1) ？ （正如dbaupp在他下面的评论中所建议的那样）
实际上，您的foldl的两个实现显着不同。 不能保证fzx需要完全遍历x来计算它的答案，所以deepseq x (fzx)可能会做不必要的工作; 此外，即使x完全评估，也不能保证fzx没有嵌套的thunk，所以let z' = deepseq x (fzx) in seq z' (foo z')可能做不到足够的工作。
您提到的问题的正确解决方案是使用foldl'和严格的数据类型作为累加器类型; 这样， seq只需要检查构造函数就可以知道整个结构是完全评估的，反过来强制构造函数会强制整个结构被完全评估。