まず、前回の記事の最後に書いたリストモナドのことについて簡単に触れておく。

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（左単位元）
2. m >>= return == m（右単位元）
3. 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 の実体が関数なのでやや面倒だが、順に確認していく。

まず、式変形のための準備をしておく。

1. (\x -> f x) = f である。
   
2. runMc (return x) s = (\s -> (x, s)) s = (x, s) である。
   
3. runMc はデータ構築子のMcDをはがして中身を取り出す関数だから、McD . runMc = id となる。

では順に見てゆく。

1. 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)より）

   となる。

2. 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)より）

   となる。

3. 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 の計算結果は捨てられるが、メモの内容は伝達されていることが分かる。

State モナド

これまではメモ化の記事で定義し使ってきた 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)。

次回はもう少しモナド則関連のことについて書いてみようと思う。