如何让foldl消耗常量内存？

Question

我们定义如下数据类型Stupid：

import qualified Data.Vector as V
import Data.List (foldl')
data Stupid = Stupid {content::V.Vector Int, ul::Int} deriving Show

现在我有两个略有不同的代码。

foldl' (\acc x->Stupid{content=(content acc) V.// [(x,x+123)],ul=1}) (Stupid {content=V.replicate 10000 10,ul=1}) $ take 100000 $ cycle [0..9999]

占用常量内存（~100M），而

foldl' (\acc x->Stupid{content=(content acc) V.// [(x,x+123)],ul=ul acc}) (Stupid {content=V.replicate 10000 10,ul=1}) $ take 100000 $ cycle [0..9999]

占用大量内存（~8G）。

理论上，在这两种情况下，整个过程只需要当前 Stupid 对象的一个副本。我不明白为什么要访问和记录 ul acc.

内存消耗会有这么大的差异

如果我需要访问 ul acc，有人可以解释为什么会发生这种情况并提供常量内存的解决方法吗？谢谢。

注意：我知道我可以批量替换向量，这个脚本只是为了演示目的，所以请不要修改那部分。

Answer 1

我会尝试强制 Stupid 的字段，看看是否有帮助。

let f acc x = c `seq` a `seq` Stupid{content=c,ul=a}
       where
       c = content acc V.// [(x,x+123)]
       a = ul acc
in foldl' f (Stupid {content=V.replicate 10000 10,ul=1}) $
   take 100000 $
   cycle [0..9999]

这应该几乎等同于强制函数的参数：

foldl' (\acc x -> acc `seq` x `seq` 
        Stupid{content=(content acc) V.// [(x,x+123)],ul=ul acc})
   (Stupid {content=V.replicate 10000 10,ul=1}) $ take 100000 $ cycle [0..9999]

（这也可以用 bang 模式来写，如果有人喜欢的话。）

另一种更积极的选择是在 Stupid 构造函数的定义中使用严格注释。

data ... = Stupid { content = ! someType , ul :: ! someOtherType }

这将始终在整个程序中强制使用这些字段。

如何让foldl消耗常量内存？

How to make foldl consume constant memory?

haskell

memory-management

fold