Проблема с монадой Writer в том, что она >>= не является хвостовой рекурсивной:
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')
Как видите, для оценки mappend необходимо оценить как m, так и k a, что означает, что весь стек рекурсивных вызовов должен быть принудительно обработан, прежде чем можно будет оценить первую mappend. Я считаю, что независимо от строгости, монада Writer вызовет переполнение стека в вашем определении (или его можно избежать с помощью lazy version как-нибудь?).
Если вы все еще хотите использовать монады, вы можете попробовать 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, но похоже, что определить ContT для MonadWriter невозможно