空间泄漏、写入器和总和（哦，我的上帝！）

Question

空间泄漏、写入器和总和（哦，我的上帝！）

25

我最近一直在使用Writer Monad，但是遇到了一个看起来像是空间泄漏的问题。由于我对这些东西的理解还不够深入，所以我想知道这里到底发生了什么，以及如何解决它。

首先，这里是我触发这个错误的方法：

import Control.Monad.Writer
import Data.Monoid

foo :: Integer -> Writer (Sum Integer) Integer
foo 0 = return 0
foo x = tell (Sum x) >> foo (pred x)

main = print $ runWriter $ foo 1000000

我得到：

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

为了更好地理解这一点，我重新实现了类似的功能，没有使用Writer或Sum。如果我保持事情懒惰，我会得到相同的错误：

为了更好地理解此内容，我重新实现了类似的功能，但没有使用Writer或Sum。如果我保持事情慵懒，我将得到相同的错误：

bar :: Integer -> (Integer, Integer)
bar x = bar' 0 x
    where bar' c 0 = (0, c)
          bar' c x = bar' (c + x) (pred x)

但是我可以通过将seq添加到等式中来解决这个问题：

bar' c x = c `seq` bar' (c + x) (pred x)

我尝试过对我的foo函数中的各个部分进行seq，但这似乎没有帮助。此外，我也尝试使用Control.Monad.Writer.Strict，但并没有什么改变。

是否需要以某种方式使Sum在严格意义下执行？或者我完全错了些什么？

注:

我可能在术语上有所错误。根据Space leak zoo，我的问题将被归类为“堆栈溢出”，如果是这种情况，我如何将foo转换为更迭风格？我的手动递归是否是问题所在？
阅读Haskell Space Overflow后，我想用-O2编译，只是为了看看会发生什么。这可能是另一个问题的话题，但是通过优化，甚至我的seq'd bar函数也无法运行。更新：如果我添加-fno-full-laziness，问题就消失了。

- Adam Wagner

2

Sum 是一个 newtype，因此它的严格程度或惰性程度与底层类型相同。 - hammar

3个回答

7

请查看严格写作者单子的源代码：http://hackage.haskell.org/packages/archive/transformers/0.2.2.0/doc/html/src/Control-Monad-Trans-Writer-Strict.html#line-122。

与懒惰写作者的不同之处在于，在后者中，模式匹配是懒惰的，但在两种情况下，都没有强制执行操作或迄今为止作者的"状态"。要解决您的问题，您需要一个“超严格”的作家。

- sclv

所以我假设，由于没有这样的Writer存在，我的方法是错误的？我不需要特别用于任何东西，只是为了更好地理解测试边界。 - Adam Wagner

有没有理由不能存在一个更严格的编写者？我写了这个，但还没有尝试过： https://github.com/Blaisorblade/pts/commit/29b59f0c9f869a7db83133e7f31cd9efe40ee98c#diff-f8379ae3302d3d9e41dd56fd896ef630R144 - Blaisorblade

4

我认为您的理解是正确的。

我对以下这些函数感兴趣：

bar :: Integer -> (Integer, Integer)
bar x = bar' 0 x
    where bar' c 0 = (0, c)
          bar' c x = c `seq` bar' (c + x) (pred x)
      --  bar' c x = let c' = c+x in c' `seq` bar' c' (pred x)
      --  bar' !c !x = bar' (c+x) (pred x)

当使用优化编译时，会产生堆栈溢出，尽管相关函数：

bar2 :: Integer -> (Integer, Integer)
bar2 x = bar' 0 x
     where bar' c 0 = (0, c)
           bar' !c !x = let c' = c+x in c' `seq` bar' c' (pred x)

bar3 :: Integer -> Integer
bar3 x = bar' 0 x
     where bar' c 0 = c
           bar' c x = c `seq` bar' (c + x) (pred x)

bar4 :: Integer -> (Integer, Integer)
bar4 x = (0, bar' 0 x)
     where bar' c 0 = c
           bar' c x = c `seq` bar' (c + x) (pred x)

不要这样做。

我认为这看起来像是 GHC 优化器中的一个 bug，你应该报告它。从查看核心代码（使用-ddump-simpl生成）来看，在溢出函数中，并不是所有情况下都会严格评估c参数。我找到的最接近原始版本的工作版本是bar2，但我认为它过度规定了。

由于你有一个非常简单的测试用例，因此很有可能会修复它。

- John L

我在 GHC 的 trac 上找到了这个票：http://hackage.haskell.org/trac/ghc/ticket/5262。我假设这是同一个 bug。 - Adam Wagner

@AdamWagner：看起来是这样。加上“-fno-full-laziness”对我来说解决了泄漏问题。 - John L

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ed'ka · Accepted Answer

Writer Monad的问题在于它的>>=不是尾递归的。

instance (Monoid w, Monad m) => Monad (WriterT w m) where
m >>= k  = WriterT $ do
    (a, w)  <- runWriterT m
    (b, w') <- runWriterT (k a)
    return (b, w `mappend` w')

正如你所看到的，它必须评估m和k a两个部分才能评估mappend，这意味着在第一个mappend被评估之前，整个递归调用堆栈都必须被强制执行。我相信，无论是否严格，写入器单子都会导致定义中出现堆栈溢出（或者可以用某种方式避免使用lazy版本吗？）。

如果你仍然想要使用单子，你可以尝试使用State，它是尾递归的。其中包括带有严格put的严格版本：

import Control.Monad.State.Strict

foo :: Integer -> State (Sum Integer) Integer
foo 0 = return 0
foo x = do
   w <- get
   put $! w `mappend` (Sum x)
   foo (pred x)

main = print $ (`execState` Sum 0) $ foo 1000000

或者采用延续传递风格（CPS）的懒惰版本：

import Control.Monad.Cont
import Control.Monad.State.Lazy

foo :: Integer -> ContT Integer (State (Sum Integer)) Integer
foo 0 = return 0
foo x = do
  w <- get
  put $! w `mappend` (Sum x)
  foo (pred x)

main = print $ ((`execState`Sum 0) . (`runContT`return)) $ foo 1000000

tell 的方便类比：

stell :: (MonadState w m, Monoid w) => w -> m ()
stell a = get >>= \w -> put $! w `mappend` a

我怀疑如果能够在Writer中使用ContT，那么CPS也将有助于我们使用Writer，但看起来不可能为MonadWriter定义ContT：define ContT for MonadWriter：