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を使ってはならないという話があります。
理由は単純で、スペースリークが発生するためです。


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

```hs
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
```

結果は以下です:

```hs
-- 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にあります。

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

[^1]: http://qiita.com/ruicc/items/553119c6586884c785a0

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

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

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

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

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

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

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

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

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

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

[^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


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

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

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

```hs
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`であるケースを考えてください。

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

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

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

```hs
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
```

結果:

```hs
-- 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使いましょう。