Более строгий контроль.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'' <> ...)) и в данном случае это Map.union, которое является строгим в корешке карты. Поэтому, если я создам большую последовательность объединений, все это должно быть оценено, как только я форсирую карту, которая переполняет стек.

Мы хотим, чтобы союзы выполнялись раньше. Нам нужен более строгий 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'')

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


lazy-evaluation haskell strictness monad-transformers
person Lambdageek    schedule 09.09.2014    source источник
comment
Это уже встречалось в утечке пространства в Pipes с RWST, однако я не У меня нет ответа на проблему со стандартной библиотекой. «Почему бы и нет» может быть слишком самоуверенным.   -  person Zeta    schedule 09.09.2014
comment
Ну, почему бы и нет, в основном ожидал ответов, что этого нет в библиотеке, потому что вы нарушили законы монад, когда сделали его слишком строгим, или по какой-то аналогичной технической причине. Не что-то вроде, потому что [мнение].   -  person Lambdageek    schedule 11.09.2014

Ответы (1)


arrow_upward
16
arrow_downward

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

person Gabriel Gonzalez    schedule 09.09.2014
comment
Это доступно как библиотека сейчас? - person user3237465; 09.12.2016
comment
@ user3237465 Существует writer-cps-mtl (или writer-cps-full, если вам нужно несколько дополнительных экземпляров lens и mmorph). - person duplode; 23.03.2017