Космические утечки, писатели и сумы (о, мой!)

Недавно я играл с 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.

Чтобы понять это лучше, я реализовал аналогичную функциональность без писателя или суммы, и если я буду держать все хорошо и лениво, я получаю такая же ошибка:

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 быть строгим? Или я чего-то не хватает совершенно разные?

Примечания

Возможно, у меня есть моя терминология. Согласно Космическая утечка зоопарк, моя проблема будет классифицирована как "переполнение стека", и если что случай, как бы преобразовать foo в более итеративный стиль? Является ли мое руководство рекурсия проблема?
После прочтения Haskell Space Overflow у меня было идея скомпилировать с -O2, просто чтобы узнать, что происходит. Это может быть тема для другой вопрос, но с оптимизацией даже моя функция seq 'd bar не запускается. Обновление. Эта проблема исчезает, если я добавляю -fno-full-laziness.

Ответ 1

Проблема с монадой 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')

Как вы можете видеть, он должен оценивать как m, так и k a для оценки mappend, что означает, что весь пакет рекурсивных вызовов должен быть принудительно до того, как будет оценен первый mappend. Я считаю, что независимо от строгости Writer 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 для MonadWriter:

Ответ 2

Посмотрите на источник для строгой монады писателя: http://hackage.haskell.org/packages/archive/transformers/0.2.2.0/doc/html/src/Control-Monad-Trans-Writer-Strict.html#line-122

Отличие от ленивого автора заключается в том, что в последнем случае совпадение шаблонов является ленивым, но ни в одном случае операция mappend или "состояние" писателя до сих пор не принудительно. Чтобы решить вашу проблему, вам понадобится "супер-строгий" писатель.

Ответ 3

Я думаю, что ваше понимание верное.

Мне интересно, как эти функции:

bar :: Integer -> (Integer, Integer)
bar x = bar' 0 x
    where bar' c 0 = (0, c)
          bar' c x = c `seq` bar' (c + x) (pred x)
      --  bar' c x = let c' = c+x in c' `seq` bar' c' (pred x)
      --  bar' !c !x = bar' (c+x) (pred x)

создает переполнение стека при компиляции с оптимизацией, хотя связанные функции:

bar2 :: Integer -> (Integer, Integer)
bar2 x = bar' 0 x
     where bar' c 0 = (0, c)
           bar' !c !x = let c' = c+x in c' `seq` bar' c' (pred x)

bar3 :: Integer -> Integer
bar3 x = bar' 0 x
     where bar' c 0 = c
           bar' c x = c `seq` bar' (c + x) (pred x)

bar4 :: Integer -> (Integer, Integer)
bar4 x = (0, bar' 0 x)
     where bar' c 0 = c
           bar' c x = c `seq` bar' (c + x) (pred x)

нет.

Я думаю, что это похоже на ошибку в оптимизаторе GHC, и вы должны сообщить об этом. Если посмотреть на ядро (созданное с помощью -ddump-simpl), аргумент c не будет строго оцениваться во всех случаях для переполняющих функций. bar2 - самая близкая рабочая версия, которую я нашел в оригинале, и мне кажется, что она не указана.

Поскольку у вас очень простой тестовый сценарий, есть хорошие шансы, что он будет исправлен.