空间泄漏,作家和总和(哦,我的!)

Question

我最近一直在玩作家莫纳德,我遇到了似乎是空间泄漏的事情.我不能说我完全理解这些事情,所以我想知道这里发生了什么,以及如何解决它.

首先,这是我如何触发此错误:

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的情况下重新实现了类似的功能,如果我保持良好和懒惰,我会得到同样的错误:

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)

我已经尝试seq了我的各种foo功能,但这似乎没有帮助.此外,我尝试过使用,Control.Monad.Writer.Strict但这也没有什么区别.

是否Sum需要严格不知何故？还是我错过了一些完全不同的东西？

笔记

• 我这里的术语可能不对.根据Space leak zoo,我的问题将被归类为"堆栈溢出",如果是这种情况,我将如何转换foo为更迭代的样式？我的手动递归是问题吗？
• 在阅读Haskell Space Overflow之后,我有了编译的想法-O2,只是为了看看会发生什么.这可能是另一个问题的主题,但是通过优化,即使我的seq'd bar函数也无法运行. 更新:如果我添加,这个问题就消失了-fno-full-laziness.

Answer 1

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被评估之前必须强制执行整个递归调用堆栈.我相信,无论严格性如何,Writer monad都会在你的定义中导致堆栈溢出(或者可以用某种方式避免使用懒惰版本？).

如果你仍然想使用monad,你可以尝试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

我怀疑,如果有可能使用ContT与WriterCPS将帮助我们Writer为好,但看起来是不可能的定义ContT为MonadWriter:

Answer 2

看看源的严格作家单子:http://hackage.haskell.org/packages/archive/transformers/0.2.2.0/doc/html/src/Control-Monad-Trans-Writer-Strict.html#line- 122

与懒惰作者的不同之处在于,在后者中,模式匹配是懒惰的 - 但在任何情况下都不是作者的mappend操作或"状态"到目前为止被迫.要解决您的问题,您需要一个"超级严格"的作家.