状態をモナドで実現する方法を考えます。
リスト
例は簡単な方がいいので、データ構造として Lisp 風のリストを定義しましょう。
data List a = Nil | Cons a (List a) deriving Show
リストは、こんな風に表せます。
Cons "c" (Cons "b" (Cons "a" Nil))
Lisp 風の cons も定義してみましょう。
cons :: a -> List a -> List a cons x xs = Cons x xs cons "c" $ cons "b" $ cons "a" Nil → Cons "c" (Cons "b" (Cons "a" Nil))
状態を持つリスト
さて、この Lisp 風のリストに、要素の数を覚えさせておきたいとしましょう。もちろん、数えれば分りますが、数えなくても一瞬で分るようにしたいのです。
モナドを知らない関数型言語プログラマーなら、cons の引数を増やしてカウンターを渡して行くでしょう。これは面倒です。
命令型プログラマーなら、外部変数を用意して、cons の中でカウンターを増やすでしょう。純粋関数型プログラマーから見ると、これは許せません。
というわけで、モナドの登場です。
とりあえず定義してみる
あるデータ型 a に状態を付け加えるモナドを Monadic a と呼ぶことにしましょう。Monadic は、以下のように定義できます。
type Counter = Int data Monadic a = Monadic (Counter -> (a, Counter)) instance Monad Monadic where Monadic f >>= g = Monadic $ \cnt0 -> let (result1, cnt1) = f cnt0 Monadic h = g result1 (result2, cnt2) = h cnt1 in (result2, cnt2) return x = Monadic $ \cnt -> (x, cnt)
状態は整数(Int)です。カウンターだと分りやすいように、Counter という別名を付けています。
モナド Monadic には、Monadic というラベルが付きます。そして、これは常套手段なので、「そんなものか」と考えて欲しいのですが、Monadic は引数として「状態」を取り、「データと状態のタプル」を返す関数とします。
タプルのどちらを状態(Counter)にしようか迷う必要はありません。どちらでも、好きな方に決めればよいのです。なぜなら、return の定義によって、その位置は Haskell に理解してもらえるからです。
return は、引数としてデータ(x)を取り、Monadic、つまり Monadic というラベルの付いた関数を返します。状態を意味する引数 cnt は、誰かがよろしく与えてくれると考えて下さい。データ x はタプルの左、状態はタプルの右にあります。
この定義のお陰で、do 構文の中で "<-" を使うと、データであるタプルの左側を取り出すことができます。
最大の難関は、bind の理解です。これは、後ほど戻ってくることにしましょう。
使ってみる
Monadic な cons は、こう定義できます。
cons0 :: a -> List a -> Monadic (List a) cons0 x xs = Monadic $ \cnt -> (Cons x xs, cnt + 1)
カウンター(cnt)を1つ増やしていることに注意して下さい。
cons0 は、Monadic というラベル付きの関数ですので、そのままでは実行できません。そこで、ラベルを外して関数を実行する関数 run を定義してみます。
run :: Monadic a -> Counter -> (a, Counter) run (Monadic func) initCnt = func initCnt
カウンターをよろしく与えてくれるのは、この run なのです。
run を使ってみましょう。
triple :: Monadic (List String) triple = do a <- cons0 "a" Nil b <- cons0 "b" a c <- cons0 "c" b return c run triple 0 → (Cons "c" (Cons "b" (Cons "a" Nil)),3)
確かにカウンターが 3 になっています。
略記法
一般には、do 表記の方が分りやすいと思われているかもしれませんが、bind の方が分りやすい場合もあります。上記の例を書き換えてみましょう。
run (cons0 "a" Nil >>= cons0 "b" >>= cons0 "c") 0 → (Cons "c" (Cons "b" (Cons "a" Nil)),3)
こっちの方がすっきりしていますが、Lisp とは順番が逆なので嫌ですね。これは、左右の引数を入れ替えた bind、記号は "=<<" を使うと解消します。
run (cons0 "c" =<< cons0 "b" =<< cons0 "a" Nil) 0 → (Cons "c" (Cons "b" (Cons "a" Nil)),3)
かっこいー。
bind の意味
bind は、あるモナドと、モナドを返す関数をくっ付ける糊だと説明されることがあります。
今回の Monadic が格納しているのは関数です。関数と関数をくっ付けるので、今回の bind は、一種の関数合成になります。
以下の二つの関数があるとしましょう。
f = \cnt0 -> (result1, cnt1) g = \cnt1 -> (result2, cnt2)
この関数を("."を使うんじゃなくて)合成しろと言われたら、こう書けるでしょう。
let (result1, cnt1) = f cnt0 (result2, cnt2) = g cnt1 in (result2, cnt2)
でも、これでは result1 が g に伝わりませんね。
前出の bind の定義で、ここに当たる部分はこうなっています。
let (result1, cnt1) = f cnt0 Monadic h = g result1 (result2, cnt2) = h cnt1 in (result2, cnt2)
間に追加されている一行で、g に result1 が伝わっているのが分ります。
この一行を理解できれば、モナドへの世界が開けます。
bindの熟考
bind の定義で f がいきなり使えるのは、左側に "Monadic f" と書いてあるので、f は Monadic というラベルが外れた関数だからです。
g とはなんでしょうか？ 具体例を見る方がいいでしょう。たとえば、
cons0 "a" Nil >>= cons0 "b"
だと、g は cons0 "b" です。cons0 の定義は、
cons0 :: a -> List a -> Monadic (List a) cons0 x xs = Monadic $ \cnt -> (Cons x xs, cnt + 1)
でした。そこで cons0 "b" は、
cons0 "b" xs = Monadic $ \cnt -> (Cons "b" xs, cnt + 1)
となります。無名関数にしてみると、
cons0 "b" = \xs -> Monadic $ \cnt -> (Cons "b" xs, cnt + 1)
となります。これが g です。
つまり、g に result1 を与えた結果は、(result2, cnt2) になるのでは、なく Monadic になるのです。Monadic というラベルを外すと関数が出てきて、その関数に cnt1 を与えると、(result2, cnt2) になります。
役割分担
cons0 では、リストを作るという仕事と、カウンターを増やすという仕事の両方をしていました。これは分離すべきです。カウンターを増やす裏方を作れば、リストを作る関数は、リストを作ることに専念できるからです。
という訳で、カウンターを増やす incr1 を定義しています。
incr1 :: Monadic Int incr1 = Monadic $ \cnt -> (999, cnt + 1)
カウンターを増やすことが本質ですので、データの方はなんでもいいのですが、ここでは目立つように 999 という整数にしました。incr1 の型は、999 を返すのですから、Monadic Int になります。
incr1 を使えば、cons1 を次のように定義できます。
cons1 :: a -> List a -> Monadic (List a) cons1 x xs = do incr1 return (Cons x xs) run (cons1 "c" =<< cons1 "b" =<< cons1 "a" Nil) 0 → (Cons "c" (Cons "b" (Cons "a" Nil)),3)
Monadic Int と List a -> Monadic (List a) が糊でくっ付けられて、より大きな Monadic (List a) が生成されていることが分りますか？
要素に番号付け
さて、気が変わって、リストの要素に何番目か番号を振りたいとしましょう。すると、incr1 は適当な値ではなく、その時点でのカウンターをデータとして返す必要があります。よって、こういう定義になります。
incr2 :: Monadic Counter incr2 = Monadic $ \cnt -> (cnt, cnt + 1)
これを活用する cons はこうなります。
cons2 :: a -> List (Counter, a) -> Monadic (List (Counter, a)) cons2 x xs = do cnt <- incr2 return (Cons (cnt, x) xs) run (cons2 "c" =<< cons2 "b" =<< cons2 "a" Nil) 0 → (Cons (2,"c") (Cons (1,"b") (Cons (0,"a") Nil)),3)
put と get
incr2 はいかにもハードコーディングです。状態を得る関数 get と状態を変える関数 put に分離してみましょう。
get :: Monadic Counter get = Monadic $ \cnt -> (cnt, cnt) put :: Counter -> Monadic Counter put x = Monadic $ \cnt -> (cnt, x) cons3 :: a -> List (Counter, a) -> Monadic (List (Counter, a)) cons3 x xs = do cnt <- get put (cnt + 1) return (Cons (cnt, x) xs) run (cons3 "c" =<< cons3 "b" =<< cons3 "a" Nil) 0 → (Cons (2,"c") (Cons (1,"b") (Cons (0,"a") Nil)),3)
Stateモナド
ここまで理解できれば、これはStateモナドの再発明だったと気付くことでしょう。
import Control.Monad.State type Counter = Int data List a = Nil | Cons a (List a) deriving Show cons :: a -> List (Counter, a) -> State Counter (List (Counter, a)) cons x xs = do cnt <- get put (cnt + 1) return (Cons (cnt, x) xs) evalState (cons "c" =<< cons "b" =<< cons "a" Nil) 0 → Cons (2,"c") (Cons (1,"b") (Cons (0,"a") Nil))
おわりに
これでもモナドが分らなければ、どこが分りにくいかコメントして下さい！
