Строгий контроль .Monad.Trans.Writer.Strict

Итак, мы имеем:

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

Причина, по-моему, состоит в том, что (>>=) для Writer определяется как:

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

Если у меня большое вычисление Writer a, он создает длинную последовательность mappends: w <> (w' <> (w'' <> ...)), и в этом случае a 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'')

Итак, мой вопрос: существует ли это в какой-то "стандартной" библиотеке? Если нет, почему бы и нет?

Ответы

Ответ 1

Непосредственный ответ на ваш вопрос: нет, нет стандартной библиотеки, которая предоставляет это. Кроме того, версия, которую вы предложили, по-прежнему будет протекать. Единственная версия, которую я знаю, которая не течет, - это симулировать WriterT с помощью строгой StateT. Я написал очень подробный e-mail об этом в список рассылки библиотек 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 в какой-то момент, но есть некоторые незначительные проблемы, которые необходимо устранить (например, имя модуля должно быть для одного).