25

私は最近 Writer モナドをいじっていて、スペースリークのように見えるものに出くわしました。これらのことをまだ完全に理解しているとは言えませんので、ここで何が起こっているのか、そしてそれを修正する方法を知りたいです.

まず、このエラーをトリガーする方法は次のとおりです。

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なんか厳しくする必要ある？それとも、まったく違うものを見逃していますか？

ノート

  • ここで用語が間違っている可能性があります。Space leak Zooによると、私の問題は「スタック オーバーフロー」に分類されます。その場合、fooより反復的なスタイルに変換するにはどうすればよいですか? 私の手動再帰が問題ですか？
  • Haskell Space Overflowを読んだ後-O2、何が起こるかを確認するために、 でコンパイルするという考えが浮かびました。これは別の質問のトピックかもしれませんが、最適化すると、私seqのbar関数でさえ実行に失敗します。 更新: を追加すると、この問題はなくなり-fno-full-lazinessます。
4

3 に答える 3

12

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どちらが末尾再帰的かを試すことができます。strict を使用した厳密なバージョンのいずれか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

ContTCPS で使用することが可能であれば、同様にWriter役立つと思いますが、 MonadWriter に ContT を定義することはできないようです:Writer

于 2011-10-12T04:21:49.133 に答える
7

厳密なライターモナドのソースを見てください：http：//hackage.haskell.org/packages/archive/transformers/0.2.2.0/doc/html/src/Control-Monad-Trans-Writer-Strict.html#line- 122

怠惰なライターとの違いは、後者の場合、パターンの一致が怠惰であるということです。しかし、どちらの場合も、mappendこれまでのところ、ライターの操作または「状態」は強制されていません。問題を解決するには、「超厳格な」ライターが必要です。

于 2011-10-11T03:32:23.127 に答える
4

あなたの理解は正しいと思います。

これらがどのように機能するかに興味があります。

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私が見つけたオリジナルに最も近い動作バージョンであり、私には過剰に指定されているようです.

非常に単純なテスト ケースがあるため、修正される可能性が高くなります。

于 2011-10-11T09:29:59.387 に答える