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

Question

惰性折叠使用大量 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'仅将中间状态评估为弱头范式\xe2\x80\x94i.e. 直到第一个构造函数。这是通用函数最多能做的事情，也是所谓“严格”函数通常能做的事情。求值(x1, y1) <+> (x2, y2)直到看起来像构造函数给出(x1 + x2, y1 + y2)，其中各部分仍然未求值（它们已被 ” 保护” (,)）。通过迭代，foldl'严格保持状态为 的形式，(_, _)而不是(_, _) <+> (_, _) <+> ...，但_s 会变成巨大的未评估的形式 的项_ + _ + _ + ...。

\n

修改<+>以在公开构造函数之前评估添加内容。

\n

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

\n