为什么 foldl' 使用大量具有复杂数据结构的 RAM？

Question

Lazy fold使用大量RAM。在Data.List中，foldl'提供了使用严格评估的左折叠。例如，以下计算了1000万个零的总和，而RAM使用量几乎没有增加。

sum0 = foldl' (+) 0 (replicate 10000000 0)

然而，这似乎不适用于复杂的数据结构。例如，如果我们为数对定义加法，并计算零对的和，则RAM的使用量会显著增加：

(x1,y1) <+> (x2,y2) = (x1 + x2,y1 + y2)
sum00 = foldl' (<+>) (0,0) (replicate 10000000 (0,0))

为什么会发生这种情况？有没有办法减少RAM的使用？

Answer 1

foldl'仅将中间状态评估为弱头范式，即直到第一个构造函数。这是所能做的最多的泛型函数；严格的"；通常是这样。评估(x1, y1) <+> (x2, y2)，直到它看起来像是一个构造函数给出了(x1 + x2, y1 + y2)，其中部分仍然没有评估(它们已经被(,)"保护"(。通过迭代，严格的foldl'将状态保持在(_, _)而不是(_, _) <+> (_, _) <+> ...的形式，但_会发展成_ + _ + _ + ...形式的巨大未赋值项。

修改<+>以在公开构造函数之前对添加进行求值。

(x1, y1) <+> (x2, y2) = x `seq` y `seq` (x, y)
where x = x1 + x2; y = y1 + y2
-- or
(x1, y1) <+> (x2, y2) = ((,) $! x1 + y1) $! x2 + y2
-- or (with deepseq package)
(x1, y1) <+> (x2, y2) = force (x1 + x2, y1 + y2)
-- x `seq` y = y, but only if x reaches WHNF
-- usually, evaluating x `seq` y to WHNF evaluates x (to WHNF) before it returns the result of evaluating y to WHNF
-- though that's not the official definition of `seq`, since Haskell nominally doesn't have an evaluation strategy
-- (and GHC's actual `seq` may do something different if GHC is feeling smart)