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

Question

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

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

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просто чтобы посмотреть что получится. Это может быть тема для другого вопроса, но с оптимизацией, даже мой seqd" bar функция не запускаетсяОбновление: эта проблема исчезнет, ​​если я добавлю -fno-full-laziness,

Answer 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 вызовет переполнение стека в вашем определении (или его можно как-то избежать с помощью отложенной версии?).

Если вы все еще хотите использовать монады, вы можете попробовать 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:

Answer 2

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

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

Answer 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 это самая близкая рабочая версия, которую я нашел к оригиналу, и она кажется мне чрезмерной.

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