一个更严格的Control.Monad.Trans.Writer.Strict

Question

所以我们有:

import Control.Monad.Writer.Strict

type M a = Writer (Map Key Val) a

一些Key和Val.

只要我们不查看收集的输出,一切都可以正常工作:

report comp = do
  let (a,w) = runWriter comp
  putStrLn a

但是,如果我们想要检查w,我们会得到堆栈溢出.

 report comp = do
   let (a,w) = runWriter comp
   guard (not $ null w) $ do -- forcing w causes a stack overflow
     reportOutputs w
   putStrLn a

我认为原因是因为(>>=)for Writer 被定义为:

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

如果我有一个大的Writer a计算,它会建立一个很长的mappend序列:w <> (w' <> (w'' <> ...))在这种情况下,Map.union这是一个严格的地图脊柱.因此,如果我构建了一个大的联合序列,那么只要我强制Map溢出堆栈,就必须对整个事物进行评估.

我们想要的是尽早完成工会.我们想要一个更严格的Strict.Writer:

m >>= k = WriterT $ do
    (a, w) <- runWriterT m
    (b, w') <- runWriterT (k a)
    let w'' = w `mappend` w'
    w'' `seq` return (b, w'')

所以我的问题是:这是否存在于某些"标准"库中？如果没有,为什么不呢？

Answer 1

您问题的直接答案是:不,没有标准库提供此功能.此外,您提出的版本仍将泄露.我知道唯一不泄漏的版本是WriterT使用严格模拟StateT.我在Haskell库邮件列表中写了一篇非常详细的电子邮件,比较了几个实现的严格性和性能.简而言之:实施WriterT严格StateT不仅可以消除空间泄漏,还可以生成非常高效的代码.

这是有效的实现:

newtype WriterT w m a = WriterT { unWriterT :: w -> m (a, w) }

instance (Monad m, Monoid w) => Monad (WriterT w m) where
    return a = WriterT $ \w -> return (a, w)
    m >>= f  = WriterT $ \w -> do
        (a, w') <- unWriterT m w
        unWriterT (f a) w'

runWriterT :: (Monoid w) => WriterT w m a -> m (a, w)
runWriterT m = unWriterT m mempty

tell :: (Monad m, Monoid w) => w -> WriterT w m ()
tell w = WriterT $ \w' ->
    let wt = w `mappend` w'
     in wt `seq` return ((), w `mappend` w')

我想transformers在某些时候看到这一点,但是有一些小问题需要解决(例如模块名称应该是什么).