スペースリークとライターとサム（

Question

最近私はライターモナードと遊んでいましたが、スペースリークと思われるものが に入ってしまいました。これらのことをまだ完全に理解しているとは言い難いので、ここで何が起こっているのか、またそれを修正する方法を知りたいと思います。

まず、ここで私はこのエラーを引き起こすことができる方法は次のとおりです。

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を追加することによってこの問題を解決することができます：私は私のfoo機能のseq INGの様々なビットを試してみたが、それは助けるために を思えません

bar' c x = c `seq` bar' (c + x) (pred x) 

。また、私はControl.Monad.Writer.Strictを使ってみましたが、 でも違いはありません。

Sumは何とか厳密にする必要がありますか？または、私は何かが欠けている 全く異なる？

ノート

• 私はここに私の専門用語が間違っていてもよいです。 Space leak zooによれば、私の問題は「スタックオーバーフロー」に分類され、 の場合、どのようにしてより反復的なスタイルに変換するのですか？foo私のマニュアル 再帰は問題ですか？
• Haskell Space Overflowを読んだ後、-O2とコンパイルするアイデアは、ちょうど何が起こるかを見るために でした。これは の別の質問ですが、最適化を使用すると、seqのd bar機能さえ実行できません。 更新：-fno-full-lazinessを追加するとこの問題は解決します。厳密ライターモナドのソースで

Answer 1

ライターモナドでの問題は、それが>>=だということですが末尾再帰ではありません。

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のモナドがあなたの定義にスタックオーバーフローを引き起こすと信じています（または、何とかの怠惰なバージョンで避けることができますか？）。

モナドをまだ使用したい場合は、テール再帰的な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でもお手伝いしますが、pではないようですossible to define ContT for MonadWriter：

Answer 2

ルック：http://hackage.haskell.org/packages/archive/transformers/0.2.2.0/doc/html/src/Control-Monad-Trans-Writer-Strict.html#line-122

レイジーライタとの違いは、後者では、パターン一致が遅延していることである - しかし、どちらの場合に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のオプティマイザのバグのようですが、report itとする必要があります。 （-ddump-simplで生成された）コアを見ると、あふれ関数のすべての場合において、引数は厳密には評価されません。 は、元のバージョンに最も近いバージョンです。

非常に簡単なテストケースがあるので、修正される可能性が高いです。