12

したがって、次のようになります。

import Control.Monad.Writer.Strict

type M a = Writer (Map Key Val) a

いくつかのKeyとVal。

収集された出力を見ない限り、すべて問題なく動作します。

report comp = do
  let (a,w) = runWriter comp
  putStrLn a

ただし、 を調べたい場合はw、スタック オーバーフローが発生します。

 report comp = do
   let (a,w) = runWriter comp
   guard (not $ null w) $ do -- forcing w causes a stack overflow
     reportOutputs w
   putStrLn a

(>>=)その理由は、 forWriter が次のように定義されているためだと思います。

m >>= k  = WriterT $ do
    (a, w)  <- runWriterT m
    (b, w') <- runWriterT (k a)
    return (b, w `mappend` w')

大規模なWriter a計算を行うと、長い一連の mappend が作成されます。w <> (w' <> (w'' <> ...))この場合、Map.unionこれはマップの背骨で厳密な a です。したがって、ユニオンの大きなシーケンスを構築する場合、スタックをオーバーフローする Map を強制するとすぐに、すべてを評価する必要があります。

私たちが望むのは、結合を早期に実行することです。より厳密な Strict.Writer が必要です。

m >>= k = WriterT $ do
    (a, w) <- runWriterT m
    (b, w') <- runWriterT (k a)
    let w'' = w `mappend` w'
    w'' `seq` return (b, w'')

だから私の質問は:これはいくつかの「標準」ライブラリに存在しますか? そうでない場合、なぜですか？

4

1 に答える 1

16

あなたの質問に対する即時の答えは次のとおりです。いいえ、これを提供する標準ライブラリはありません。また、提案したバージョンは引き続きリークします。私が知っているリークしない唯一のバージョンはWriterT、strict を使用してシミュレートすることStateTです。これについて、いくつかの実装の厳密さとパフォーマンスを比較する非常に詳細な電子メールを Haskell ライブラリ メーリング リストに書きました。簡単に言うWriterTと、strict として実装すると、StateTスペース リークがなくなるだけでなく、非常に効率的なコードが生成されます。

機能した実装は次のとおりです。

newtype WriterT w m a = WriterT { unWriterT :: w -> m (a, w) }

instance (Monad m, Monoid w) => Monad (WriterT w m) where
    return a = WriterT $ \w -> return (a, w)
    m >>= f  = WriterT $ \w -> do
        (a, w') <- unWriterT m w
        unWriterT (f a) w'

runWriterT :: (Monoid w) => WriterT w m a -> m (a, w)
runWriterT m = unWriterT m mempty

tell :: (Monad m, Monoid w) => w -> WriterT w m ()
tell w = WriterT $ \w' ->
    let wt = w `mappend` w'
     in wt `seq` return ((), w `mappend` w')

いつかこれが追加されることを望んtransformersでいますが、解決する必要がある小さな問題がいくつかあります (たとえば、モジュール名はどうあるべきか)。

于 2014-09-09T17:19:23.497 に答える