この記事は Haskell (その2) Advent Calendar 2017 の10日目の記事です。あけましておめでとうございます。
今回は ListT モナド変換子 について調べたことをまとめます。
hackage で検索をすると ListT と名の付くモナド変換子を提供しているパッケージは4つほど見つかります。
このうち mtl パッケージで提供している ListT は transformers パッケージからインポートされているだけなので実装としては同一のものです。
また、pipes パッケージで提供されているものは Pipes と組み合わせて使うもののようで、単独で List モナドの変換子版というわけではなさそうです。
さらにさらに、 transformers パッケージの Control.Monad.Trans.List のドキュメント を見にいくとページ先頭に赤字で不穏な注釈が書かれています。
Deprecated: This transformer is invalid on most monads
(非推奨：このモナド変換子はほとんどのモナドに対して無効です)
非常に不穏ですね。
ただ、これだけの情報ではなぜ transformers パッケージの実装ではダメなのか、代わりに何を使えばいいのか分かりません。
ListT done right を読む
transformers パッケージの ListT について、ListT done right に詳しく書かれています。
要点をかいつまむと、
- 従来の
ListT は過剰な正格性を課している
- 従来の
ListT はいわゆるモナド変換子ではない。 m がモナドであっても ListT m がモナドになるとは限らない
- なので、上記の欠点を解消したバージョンの実装を提案する
- 新しい実装をさらに洗練させてパッケージにまとめたものが list-t である
というわけで、
TL;DR な方のために結論を書いておくと、transformers パッケージの実装はいろいろと間違っているので list-t パッケージの方を使おう ということみたいです。
テストプログラムで ListT を比べる
ListT done right には transformers パッケージの実装が正しく動かないことを示すテストのプログラムが挙げられています。
引用して、実際に実行出来るかたちにまとめてみました。パッケージ毎に結果を見てみましょう。今回は transformers と list-t を比べてみます。
github.com
いつものとおり全てのコードは GitHub に置いておきます。
1. Sum of squares - 平方和
整数 n を与えると二平方の和で n に等しくなる組を探すプログラムです。
例えば、 5 を与えると (1, 4) と (4, 1) が答えになります。
testSumOfSquares :: Int -> ListT IO (Int, Int)
testSumOfSquares n = do
let squares = liftList . takeWhile (<= n) $ map (^ (2 :: Int)) [0 ..]
x <- squares
y <- squares
lift $ print (x, y)
guard $ x + y == n
lift $ putStrLn "Sum of Squares."
return (x, y)
runTestSumOfSquares :: Int -> IO (Int, Int)
runTestSumOfSquares = fmap fromJust . ListT.head . testSumOfSquares
これ自体、リスト内包表記などでシンプルに実装できそうな処理ですが、今回は ListT IO を使って平方和の探索の途中途中で標準出力を挟むようにしてあります。
さて、testSumOfSquares は全ての答えをリストで返してくれますが、もし答えが複数あってそのうち 最初の解だけ が必要なときにはどうでしょうか。
リストから最初の要素だけを取り出すことは簡単です。問題は 遅延評価のアイデアに従って最初の答えを得るために必要な IO アクションだけ実行されて欲しい という部分です。
では見てみましょう。
実行結果 : Control.Monad.Trans.List.ListT from transformers
ghci> FromTransformers.runTestSumOfSquares 5
(0,0)
(0,1)
(0,4)
(1,0)
(1,1)
(1,4)
Sum of Squares.
(4,0)
(4,1)
Sum of Squares.
(4,4)
(1,4)
候補となる全ての組 (0,0),(0,1),(0,4), ... ,(4,1),(4,4) をまとめて探索しつくしている様が見られます。
今回は候補となる組が有限なのでいいですが、候補となる組が無限リストで与えられた場合には上手く動作しないでしょう。
実行結果 : ListT.ListT from list-t
ghci> FromListT.runTestSumOfSquares 5
(0,0)
(0,1)
(0,4)
(1,0)
(1,1)
(1,4)
Sum of Squares.
(1,4)
答えとなる最初の組 (1,4) が見つかった時点で、残りの IO アクションは実行されずに捨てられています。
こちらが望ましい動作ですね。
これは list-t パッケージが uncons :: ListT m a -> m (Maybe (a, ListT m a)) という関数を提供しているおかげです。
uncons は先頭の要素を得るのに必要な分だけ内側のモナドを実行します。
2. Grouping effects - 結合効果
今度は モナド則のうち結合則が破れる という例です。
モナドの結合則とは、
(m >>= f) >>= g == m >>= (\x -> f x >>= g)
のことです。
testGroupingEffects1 :: ListT IO Int
testGroupingEffects1 = do
r <- liftIO $ newIORef 0
(next r `mplus` next r >> next r `mplus` next r) >> next r `mplus` next r
runTestGroupingEffects1 :: IO [Int]
runTestGroupingEffects1 = toList testGroupingEffects1
testGroupingEffects2 :: ListT IO Int
testGroupingEffects2 = do
r <- liftIO $ newIORef 0
next r `mplus` next r >> (next r `mplus` next r >> next r `mplus` next r)
runTestGroupingEffects2 :: IO [Int]
runTestGroupingEffects2 = toList testGroupingEffects2
next :: IORef Int -> ListT IO Int
next r = liftIO $ do
x <- readIORef r
writeIORef r (x + 1)
return x
本来であれば runTestGroupingEffects1 と runTestGroupingEffects2 の実行結果は等しくなるはずです。
実行結果 : Control.Monad.Trans.List.ListT from transformers
ghci> FromTransformers.runTestGroupingEffects1
[6,7,8,9,10,11,12,13]
ghci> FromTransformers.runTestGroupingEffects2
[4,5,6,7,10,11,12,13]
transformers パッケージの実装ではモナドの結合則が破れていることが確認できました。
これは m がモナドであっても ListT m がモナドになるとは限らない ということを意味します。
実行結果 : ListT.ListT from list-t
ghci> FromListT.runTestGroupingEffects1
[2,3,5,6,9,10,12,13]
ghci> FromListT.runTestGroupingEffects2
[2,3,5,6,9,10,12,13]
list-t の方は正しく動作しています。
3. Order of printing - 印字順
リスト操作の中でも頻繁に使うものの中にリストの結合 (++) があります。
ListT の結合は MonadPlus クラスの mplus メソッドで代用できますが、transformers パッケージの実装では mplus が正しく動かないという例です。
a, b, c :: ListT IO ()
[a, b, c] = map (liftIO . putChar) ['a', 'b', 'c']
testOrderOfPrinting1 :: ListT IO ()
testOrderOfPrinting1 = ((a `mplus` a) >> b) >> c
runTestOrderOfPrinting1 :: IO (Maybe ((), ListT IO ()))
runTestOrderOfPrinting1 = runListT' testOrderOfPrinting1
testOrderOfPrinting2 :: ListT IO ()
testOrderOfPrinting2 = (a `mplus` a) >> (b >> c)
runTestOrderOfPrinting2 :: IO (Maybe ((), ListT IO ()))
runTestOrderOfPrinting2 = runListT' testOrderOfPrinting2
testOrderOfPrinting1, testOrderOfPrinting2 とも、正しく実装されていれば [putChar 'a' >> putChar 'b' >> putChar 'c', putChar 'a' >> putChar 'b' >> putChar 'c'] みたいな IO アクションを生成してくれるはずです。
実行結果 : Control.Monad.Trans.List.ListT from transformers
ghci> FromTransformers.runTestOrderOfPrinting1
aabbcc
ghci> FromTransformers.runTestOrderOfPrinting2
aabcbc
リストを構成する時点で IO アクションが実行されてしまうためにこのような印字になってしまうようです。
実行結果 : ListT.ListT from list-t
ghci> FromListT.runTestOrderOfPrinting1
abc
ghci> FromListT.runTestOrderOfPrinting1
abc
いい感じですね。
4. Order of ListT []
これまでの例は全て ListT IO に関するものでした。
IO モナドを含まないシンプルな例でもモナドの結合則が破れることを示すために ListT [] の例が示してあります。
v :: Int -> ListT [] Int
v 0 = ListT [0, 1]
v 1 = ListT [[0], [1]]
runTestOrderOfListTList1 :: IO ()
runTestOrderOfListTList1 = print $ toList $ ((v >=> v) >=> v) 0
runTestOrderOfListTList2 :: IO ()
runTestOrderOfListTList2 = print $ toList $ (v >=> (v >=> v)) 0
なんだかややこしそうですが、 ((v >=> v) >=> v) 0 と (v >=> (v >=> v)) 0 が等しくなるかどうかを確かめるだけのプログラムです。
実行結果 : Control.Monad.Trans.List.ListT from transformers
ghci> FromTransformers.runTestOrderOfListTList1
[[0,1,0,0,1],[0,1,1,0,1],[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1]]
ghci> FromTransformers.runTestOrderOfListTList2
[[0,1,0,0,1],[0,1,0,0],[0,1,0,1],[0,1,1,0,1],[0,1,1,0],[0,1,1,1]]
transformers パッケージの実装では結合則が破れていることを確かめられました。
実行結果 : ListT.ListT from list-t
ghci> FromListT.runTestOrderOfListTList1
[[1,0,0,1,0],[1,0,1,1,0],[0,0,1,0],[0,1,1,0],[1,0,1,0],[1,1,1,0]]
ghci> FromListT.runTestOrderOfListTList2
[[1,0,0,1,0],[1,0,1,1,0],[0,0,1,0],[0,1,1,0],[1,0,1,0],[1,1,1,0]]
バッチリですね。
まとめ
というわけで、 ListT done right に挙げられている例を実際のプログラムで確かめることができました。
また、 transformers と mtl の動作が全く同じになる事も確かめています。
さて、ここまできて確かめられていないこと、それは、
- list-t パッケージの実装なら全てのモナド
m に対して ListT m がモナドになるの？
ということですね。こちらは追試が必要そうです。
(>>=) の実装から運算によって確かめられないかと思って手を動かしてみたのですが、私の運算力では無理でした。
どなたかご存知の方がいれば情報ください。
私からは以上です。
