haskell - 使用scanl时空间泄漏在哪里？ ( haskell )

Question

考虑这段代码:

incState state i = map (+ i) state

main =
  sequence_ $ do
    n <- map last $ scanl incState (replicate 1000000 0) (repeat 1)
    return $ print $ n

当我运行它时，内存使用量不断增加，因为它打印出数字。这里的内存泄漏在哪里？它应该只保持恒定的内存量，以前的值 state每当它打印一些东西时都应该被丢弃。

即使 sequence_或者列表 monad 持有 n 的值，即每次迭代只有一个整数。我看到 6Gs 的内存在它只计数到 100 之后被使用。一百万个整数最多应该只占用 10Ms。

Answer 1

没有什么会迫使中间计算通过列表的中间。如果更换 last与 sum它停止泄漏内存。

为了看看发生了什么，让我们考虑一下对同一件事的稍微简单的陈述:

main = mapM (print . last) $ scanl incState (replicate 5 0) (repeat 1)

现在，让我们开始评估它。首先，我们状态的内存看起来像

scanl incState (map (+1) (replicate 5 0)) (repeat 1)

我们将跳过一些细节，但我们的第一个需求是 mapM模式与状态列表的开头匹配。

(:) -> replicate 5 0 
 |     ^
 |     |_________________                     
 v                       |
scanl incState (map (+1) | ) (repeat 1)

获取 last项目到 print ，我们强制列表的脊椎和最后一个项目，但不是单个项目。我们将在下一步中更好地看到这一点。

       0 : 0 : 0 : 0 : 0 : [] 
       ^
       |_________________                     
                         |
scanl incState (map (+1) | ) (repeat 1)

下一步 mapM ，我们需要状态列表中的下一项。内存现在看起来像

       0 : 0 : 0 : 0 : 0 : [] 
       ^
       |________                    
                |
(:) -> map (+1) |
 |     ^
 |     |_________________                     
 v                       |
scanl incState (map (+1) | ) (repeat 1)

获取 last项目到 print ，我们强制列表的脊椎和最后一个项目，而不是其他单个项目。

       0   : 0   : 0   : 0   : 0 : [] 
       ^     ^     ^     ^
       |     |     |     |     
       |+1 : |+1 : |+1 : |+1 : 1 : []
       ^
       |_________________                     
                         |
scanl incState (map (+1) | ) (repeat 1)

下一步 mapM ，我们需要状态列表中的下一项。内存现在看起来像

       0   : 0   : 0   : 0   : 0 : [] 
       ^     ^     ^     ^
       |     |     |     |     
       |+1 : |+1 : |+1 : |+1 : 1 : []
       ^
       |________                    
                |
(:) -> map (+1) |
 |     ^
 |     |_________________                     
 v                       |
scanl incState (map (+1) | ) (repeat 1)

获取 last项目到 print ，我们强制列表的脊椎和最后一个项目，而不是其他单个项目。

       0   : 0   : 0   : 0   : 0 : [] 
       ^     ^     ^     ^
       |     |     |     |     
       |+1 : |+1 : |+1 : |+1 : 1 : []
       ^     ^     ^     ^
       |     |     |     |     
       |+1 : |+1 : |+1 : |+1 : 2 : []
       ^
       |_________________                     
                         |
scanl incState (map (+1) | ) (repeat 1)

每次重复此操作时，我们都会留下另一个 thunk 列表，引用之前的 thunk 列表，等等。这就是空间泄漏的来源。如果您在每一步之后强制执行所有结果，例如 print . sum会做，不会有空间泄漏。