Writerを使ってはならない

2022-05-20追記:

mtl-2.3, transformers-0.5.6以降においてリークの起こらないCPS版Writerが提供されているのでそちらを用いてください:

• https://hackage.haskell.org/package/mtl-2.3/docs/Control-Monad-Writer-CPS.html
• https://hackage.haskell.org/package/transformers-0.5.6.0/docs/Control-Monad-Trans-Writer-CPS.html

Writer Monadの問題点

Haskell スペースリーク アドベントカレンダーX日目(X ~ 360)です。

Writer Monadを使ってはならないという話があります。
理由は単純で、スペースリークが発生するためです。

以下の単純なアクションを評価してみます。

import Control.Monad.Trans.Writer.Strict as SW
import Debug.Trace
import Data.Monoid

main = do
    let (c, w') = SW.runWriter (strictWriterAction 4)
    putStrLn "-- print strict writer result"
    print c
    putStrLn "-- print strict writer log"
    print w'

strictWriterAction :: Int -> SW.Writer (Sum Int) Int
strictWriterAction x = do
    y <- trace "action1" (return $ trace "value1" x)
    z <- trace "action2" (return $ trace "value2" y)
    w <- trace "action3" (return $ trace "value3" z)
    trace "tell1" (SW.tell $ trace "sum1" (Sum 1))
    trace "tell2" (SW.tell $ trace "sum2" (Sum 2))
    trace "tell3" (SW.tell $ trace "sum3" (Sum 3))
    return w

結果は以下です:

-- print strict writer result
action1
action2
action3
tell1
tell2
tell3
value3
value2
value1
4
-- print strict writer log
sum1
sum2
sum3
Sum {getSum = 6}

お分かりでしょうか。
writerのlog結果を評価しようとしたタイミングでtellの引数の評価が行われています。
言い換えると、writerのlogの結果を評価しようとしないとサンクが評価されません。
もう少し言うと、tellを実行した回数だけlogにサンクが積もり続けます。

この原因はWriterにあります。

まずアクション自体の評価と、アクションの結果やアクションの引数の評価は別に考えなければならない、と去年やりました。¹

• アクションは必要呼びで実行される (Control.Monad.Trans.Writer.Lazyの場合)
• アクションは並べた順番に実行される (Control.Monad.Trans.Writer.Strictの場合)
• アクション引数や結果は必要に応じて評価される

また、parametricな関数はサンクが積もり易いのでした。²

Writer(WriterT)の型定義は以下です。

newtype WriterT w m a = WriterT { runWriterT :: m (a, w) }

m :: * -> * はモナドなのでサンクが積もり様がないですが、a, wはともにサンクが積もりやすそうな構造になっています。

aにサンクが積もりやすいのはモナドの構造上、どれも一緒です。前述の通り、アクション結果は必要に応じてのみ、評価されます。

問題はwです。WriterのMonad instanceを見てみます。

instance (Monoid w, Monad m) => Monad (WriterT w m) where

    return a = writer (a, mempty)

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

ここのw `mappend` w'が問題です。関数適用はサンクを一個追加することに相当するのでした。³
よってmappendの適用はサンクを追加する行為です。そしてこの値は先ほどのwの型に相当する値です。
そしてMonoidのmappend :: Monoid w => w -> w -> wは閉じた演算であるため、スペースリークが発生しやすいのでした。⁴

また、パラメトリックな型の値は特別にseq等を使わなければ評価されることはないのでした。⁵
よってこのmappendのサンクが評価されることはありません。事実冒頭にて示した様にサンクは評価されません。

サンクを潰しながら進む>>=

このmappendのサンクがもし、>>=と共に評価されるような実装であったならば、Writerはリークがなくなります。

• https://mail.haskell.org/pipermail/libraries/2012-October/018599.html

newtype WriterT4 w m a = WriterT4 { unWriterT4 :: w -> m (a, w) }

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

runWriterT4 :: (Monoid w) => WriterT4 w m a -> m (a, w)
runWriterT4 m = unWriterT4 m mempty

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

この実装はStateモナドにseqを加えたものです。
この実装が興味深いのは、seqがtell側に加えられていて、このseqが作るサンクは>>=側の実装のtupleのパターンマッチによって壊される点です。

以下の行で、mがtellであるケースを考えてください。

    m >>= f  = WriterT4 $ \w -> do
        (a, w') <- unWriterT4 m w -- mがtellだったら?
        unWriterT4 (f a) w'

アクションの評価は引数の評価とは別に行われるのでした。アクションがまず実行されて、必要に応じて引数や返り値が評価されます。
アクションtellが実行されて、その結果はseqを含むサンクのまま返りますが、すぐ直後にtupleのパターンマッチがあるためにseqのサンクが評価され、無事mappendが評価されるというわけです。
こうやって>>=が進むたびにmappendは評価され、スペースリークが発生しなくなります。

このWriterT4を用いたサンプルコードが以下です:

main = do
    let (d, w'') = runIdentity $ runWriterT4 (stricterWriterAction 4)
    putStrLn "-- print stricter witer result"
    print d
    putStrLn "-- print stricter witer log"
    print w''

stricterWriterAction :: Int -> WriterT4 (Sum Int) Identity Int
stricterWriterAction x = do
    y <- trace "action1" (return $ trace "value1" x)
    z <- trace "action2" (return $ trace "value2" y)
    w <- trace "action3" (return $ trace "value3" z)
    trace "tell1" (tell4 $ trace "sum1" (Sum 4))
    trace "tell2" (tell4 $ trace "sum2" (Sum 5))
    trace "tell3" (tell4 $ trace "sum3" (Sum 6))
    return w

結果:

-- print stricter witer result
action1
action2
action3
tell1
sum1
tell2
sum2
tell3
sum3
value3
value2
value1
4
-- print stricter witer log
Sum {getSum = 15}

runWriterの後、結果を評価した段階でtellの引数も評価されていることがわかると思います。こうしてスペースリークは解消されました。

まとめ

以上のことが去年のHaskellスペースリークアドベントカレンダーを読むと、コードを実行しなくてもなんとなくわかる様になると思います。

• https://hackage.haskell.org/package/transformers-0.5.2.0/docs/Control-Monad-Trans-Writer-Strict.html

haddocにコンスタントスペースで走らせたいならWriterを使わずにState使えってちゃんと書いてあるのでState使いましょう。

1. http://qiita.com/ruicc/items/553119c6586884c785a0 ↩

2. http://qiita.com/ruicc/items/553119c6586884c785a0#parametricity%E3%81%A8%E9%81%85%E5%BB%B6%E8%A9%95%E4%BE%A1 ↩

3. http://qiita.com/ruicc/items/553119c6586884c785a0#parametricity%E3%81%A8%E9%81%85%E5%BB%B6%E8%A9%95%E4%BE%A1 ↩

4. http://qiita.com/ruicc/items/61dedb7099190254eace#%E3%83%A2%E3%83%8E%E3%82%A4%E3%83%89%E3%81%A8%E3%82%B9%E3%83%9A%E3%83%BC%E3%82%B9%E3%83%AA%E3%83%BC%E3%82%AF ↩

5. http://qiita.com/ruicc/items/553119c6586884c785a0#parametricity%E3%81%A8%E9%81%85%E5%BB%B6%E8%A9%95%E4%BE%A1 ↩