Haskell私的メモ Monadをリストで探る１

今回はHaskell初心者にとって理解が困難だといわれているMonadの話。

駆け足で頑張って抽象的な概念を理解しようとするのではなく、親しみ深い「リスト型」をモナドとして使ってみることで具体的な感覚を蓄積していこう、という考え。

>>=

前回FunctorとApplicativeを見てきた。Monadの概念として追加されるのは本当はこの関数だけ：

>>= :: (Monad m) => m a -> (a -> m b) -> m b

（returnはpureと同義だから無視）

具体的にリスト型で見てみると

>>= :: [a] -> (a -> [b]) -> [b]

となる。「a型の値のリスト」と「a型の値一つを引数にb型の値のリストを返す関数」を組み合わせて「b型の値のリスト」を返している。

例えばこんなリストと、リストを返す関数があったとして：

xs = [0, 10, 20]
f x = map (+x) [1..3] 

>>=の挙動というのは：

xs >>= f 
= [1, 2, 3, 11, 12, 13, 21, 22, 23]
= concat [[1,2,3], [11,12,13], [21,22,23]]
= concat $ pure f <*> xs
= concat $ f <$> xs

と、concatと<$>を合わせたものなことがわかる。「リストのリスト」のようにコンテキストがネストしていくのを、ネストするたびに引き上げて元のコンテキストのままに維持する挙動が追加されているのがApplicativeより強力なところ。

モナド則

Monadには>>=とreturnが満たすべき法則が三つある。

return a >>= g = g a
m >>= return  = m
m >>= (\x -> g x >>= h) = (m >>= g) >>= h

return = pureと考えて、最初の二つはリストに関しては比較的わかりやすい。定義と証明を触ってみる。

まずreturn a >>= g：

return a >>= g 
= pure a >>= g
= [a] >>= g
= concat $ g <$> [a]
= concat [g a]
= g a   -- g はリストを返す関数

次にm >>= return。帰納法で証明できた：

m >>= return
= m >>= pure
= concat $ pure <$> m

case []
concat $ pure <$> []
= concat []
= []
= m

case (x:xs)
concat $ pure <$> (x:xs)
= concat $ (pure x) : (pure <$> xs)
= concat $ ([x]) : (pure <$> xs)
= [x] ++ concat $ pure <$> xs
= [x] ++ xs    -- Induction
= x:xs
= m

直観的には

• returnはリストのネストを一つ増やす
• >>=はリストのネストを一つ減らす
• だから統合が成り立つ

というイメージ。

最後の法則は結合律に近くて、リストを返す関数の合成について：

m >>= (\x -> g x >>= h) = (m >>= g) >>= h

case [] 左辺
[] >>= (\x -> g x >>= h)
= concat $ (\x -> g x >>= h) <$> []
= concat []
= [] 

case [] 右辺
([] >>= g) >>= h
= concat $ h <$> ([] >>= g)
= concat $ h <$> (concat $ g <$> [])
= concat $ h <$> (concat [])
= concat $ h <$> []
= concat []
= []

case x:xs 左辺
x:xs >>= (\x -> g x >>= h)
= concat $ (\x -> g x >>= h) <$> (x:xs)
= concat $ (g x >>= h) : (\x -> g x >>= h) <$> xs
= (g x >>= h) ++ concat $ (\x -> g x >>= h) <$> xs
= (g x >>= h) ++ concat $ (\x -> g x >>= h) <$> xs
= (g x >>= h) ++ (xs >>= (\x -> g x >>= h))
= (g x >>= h) ++ (xs >>= g) >>= h  -- Induction

case x:xs 右辺
(x:xs >>= g) >>= h
= concat $ h <$> (x:xs >>= g)
= concat $ h <$> (concat $ g <$> x:xs)
= concat $ h <$> (concat $ (g x):(g <$> xs))
= concat $ h <$> ((g x) ++ concat $ g <$> xs)
= concat $ (h <$> g x) ++ h <$> (concat $ g <$> xs)
= (g x >>= h) ++ h <$> (concat $ g <$> xs)
= (g x >>= h) ++ concat (h <$> (concat $ g <$> xs))
= (g x >>= h) ++ concat (h <$> (xs >>= g))
= (g x >>= h) ++ (xs >>= g) >>= h

証明はできたし直観的にもわかるんだけど、やはり>>=を使う形ではなかなか言語化しにくい法則である。

感想

リストがモナドであることは知られているが、「なぜリストがモナドであるとうれしいのか」はあまり知られていない気がする。

今回いろいろさわってみたが、やはり「なぜリストがモナドであるとうれしいのか」はよくわからなかった。そもそも「リストを返す関数を組み合わせて各ステップごとにフラット化していく」ってあまり使う状況が思い浮かばない。

Applicativeなのがうれしいのはわかるのだが・・・

次回はそこを掘り下げつつ、sequenceやmapMなどの補助関数も使ってみたい。