haskell - 空间泄漏，作家和总和(哦，我的!)

Question

我最近一直在和 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，如果我保持良好和懒惰，我会得到
同样的错误:

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与 Writer CPS 将帮助我们 Writer也一样，但看起来不可能 define ContT for MonadWriter :