为什么 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)

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

Why does foldl' use a lot of RAM with complex data structures?

haskell

fold