まず、前回の記事の最後に書いたリストモナドのことについて簡単に触れておく。
madd [1,2] [10,20]
の結果はどうなるか?という話であった。(>>=)
を使った madd
の定義を思い出してみると、
madd ma mb = ma >>= (\a -> mb >>= (\b -> return (a + b)))
であり、リストモナドでの (>>=)
の定義は、xs >>= f = concat (map f xs)
であるから、内側のカッコの方から考えていくと、
「mb
の各要素に a
を足して return
する」という処理を ma
の各要素について行う
となる。したがって、madd [1,2] [10,20] = [11,21,12,22]
となる。これは、リスト内包表記を使って [a + b | a <- [1,2], b <- [10,20]]
と書いたのと同じ意味となる。
今回は、メモ化(4)の記事の中で定義し、モナドのインスタンスにした Mc s b
という型を例に挙げて考えてみようと思うが、その前にまず「モナド則」について触れておきたい。
何か新しい型 T a
を定義して、instance Monad T ...
とすればモナドになるかと言えばそうではなく、モナドになるための条件を満たさなければならない。この条件を「モナド則」と言い、これを満たしていなければ instance
で「モナドにしたよ!」と言い張ってもダメなのである。
「モナド則」とはどの本に書いてあるように、以下の3つの条件である1:
return a >>= k == k a
(左単位元)m >>= return == m
(右単位元)m >>= (\x -> k x >>= h) == (m >>= k) >>= h
(結合法則)ボクの場合、いきなりこれで挫折した。この内容が難しいかどうかと言う以前に、一見したときのややこしそうな印象が気持ちを挫けさせるのである。特に3番目の式は、初心者を追い払うには十分の風貌である。「結合法則って言うのなら、左辺は m >>= (k >>= h)
じゃないのか?」とシロートは思ってしまうのだが、残念ながらそれでは型が合わない。
見た目が怖くても、モナドとして使うのであればモナド則を満たしていることの確認は避けられない。メモ化の記事ではこの確認をせず、モナドになっているものとして話を進めてきたのだが、確認を先送りにしつづけるのも気持ちが良くないので、このあたりで確認しておくことにしよう。
注意 つまずいていた頃の自分でも理解できるように書いたつもりではあるが、しかし、モナドを学び始めた頃に見たらやはり拒否反応が起きたかな…という気もする。自分でモナドを定義する場合にはモナド則を満たしていることを確認しなければならないが、他人の作ったものならばとりあえず「信じて先へ進む」という態度でも良いと思う。むしろ、分からないところでずーっと引っかかって先へ進めない状態に留まるよりは、とりあえず先へ進み、時々振り返って考えたりする方が良いと思う。少し先のことに触れたり考えたりすることによって、「あ、そういうことだったのか」と理解できることも少なくないのではないだろうか。
なので、拒否反応が起きそうに感じたらモナド則の確認を飛ばして、次の「State モナド」から読み始めるのが良いと思う。
Mc
の定義を再掲する。型引数の b
を a
に変え、説明の都合上、(1)(2)の番号を付けた。
newtype Mc s a = McD { runMc :: s -> (a, s) }
instance Monad (Mc s) where
return x = McD (\s -> (x, s))
x >>= g = McD $ \s -> let (a, s1) = runMc x s -- (1)
in runMc (g a) s1 -- (2)
Mc s a
の実体が関数なのでやや面倒だが、順に確認していく。
まず、式変形のための準備をしておく。
(\x -> f x) = f
である。runMc (return x) s = (\s -> (x, s)) s = (x, s)
である。runMc
はデータ構築子のMcD
をはがして中身を取り出す関数だから、McD . runMc = id
となる。では順に見てゆく。
return a >>= k == k a
(左単位元)
(1)の部分で x = return a
とすると、let
の右辺が runMc (return a) s
となるが、これは準備(b)より (a,s)
である。したがって、
return a >>= k
= McD (\s -> runMc (k a) s) ((2)で g = k, s1 = s として)
= McD (runMc (k a)) (準備(a)より)
= (McD . runMc) (k a)
= k a (準備(c)より)
となる。
m >>= return == m
(右単位元)
(2)の部分で g = return
とすると、準備(b)より runMc (return a) s1 = (a, s1)
となる。これは(1)の runMc x s
と等しいから、
m >>= return
= McD (\s -> runMc m s)
= McD (runMc m) (準備(a)より)
= (McD . runMc) m
= m (準備(c)より)
となる。
m >>= (\x -> k x >>= h) == (m >>= k) >>= h
(結合法則)
左辺から見ていくと、(2)の g
に相当するものが (\x -> k x >>= h)
であり、これに a
を適用しているので g a = k a >>= h
となる。したがって、
左辺
= McD $ \s -> let (a, s1) = runMc m s
in runMc (k a >>= h) s1
(k a >>= h を >>= の定義にしたがって展開)
= McD $ \s -> let (a, s1) = runMc m s
in let (a2, s2) = runMc (k a) s1
in runMc (h a2) s2
(let - in の入れ子構造を整理)
= McD $ \s -> let (a, s1) = runMc m s
(a2, s2) = runMc (k a) s1
in runMc (h a2) s2
ここで、\s -> let (a, s1) = runMc m s in runMc (k a) s1
を見れば、まさに m >>= k
の定義そのものなので、上の式は、
= McD $ \s -> let (a2, s2) = runMc (m >>= k) s
in runMc (h a2) s2
= (m >>= k) >>= h
= 右辺
となる。
これでモナド則を満たしていることが確認できたのであるが、無味乾燥な計算としか映らないのは以前も今も同じである。「実践本」(p.237, p.263)によればモナド則を満たしているかどうかを検査してくれる言語もあるようだが、Haskellでは自力でやるしかない。
ちょっとしつこいかもしれないが、>>
で伝わるもの・伝わらないものをまた考えてみる。(>>)
のデフォルトの定義を Mc
の (>>=)
の定義に沿って書き換えると、
x >> y = McD $ \s -> let (_, s1) = runMc x s in runMc y s1
となる。メモ化を使ってFibonacci関数を求めたときの場合であれば、x
, y
がメモを使ってFibonacci数を求めさせる「計算」、s
が「メモ」である。runMc x s
でFibonacci数と更新された(かもしれない)メモが返されるが、Fibonacci数は捨てられて、更新されたメモ s1
が y
の計算に渡されている。「instance Monad (Mc s) ...
」としていることから容易に想像できたことだが、x >> y
では x
の計算結果は捨てられるが、メモの内容は伝達されていることが分かる。
これまではメモ化の記事で定義し使ってきた Mc
という型構築子を使ってきたが、より汎用的なものが「State モナド」としてライブラリに用意されている。このマニュアルページの末尾に使用例が書かれているが、Mc
との比較の意味も込めて、Stateモナドを使ってメモ化を実現してみる。Map
を使ったメモの実体は以前と同じである。
import Control.Monad.State
-- 抽象的に定義したメモ化関数。
type MemoFunc a b = a -> State (Memo a b) b
runMemo :: MemoFunc a b -> a -> b
runMemo f x = evalState (f x) sEmpty
memo :: Ord a => MemoFunc a b -> MemoFunc a b
memo f x = state $ \s ->
case getResult x s of
Just v -> (v, s)
Nothing -> let (v, s1) = runState (f x) s
in (v, putResult (x, v) s1)
newtype
による定義と instance
宣言が無くなっている他は、runMc
が runState
になるなど、わずかな変更である。これを以前のコードと差し替えれば、Fibonacci関数と両替問題にそのまま使える。ライブラリを使えば(信じれば)モナド則の確認をせずに済むのでとても楽である。改造したコード全体をGistに置いた(statememo.hs)。
次回はもう少しモナド則関連のことについて書いてみようと思う。
メモ化(4)でも触れたように、GHC 7.10 からはモナドにするためには Applicative のインスタンスにもしなければならなくなっているが、この件についてはいずれ触れたいと思う。なお、GHC 7.10.1 のリリース予定は2月下旬から3月下旬に変更されたようだ(マイルストーン 7.10.1)。↩