Hatena::ブログ(Diary)

あどけない話

2008-06-04

状態モナド遊び

状態をモナドで実現する方法を考えます。

リスト

例は簡単な方がいいので、データ構造として 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))

おわりに

これでもモナドが分らなければ、どこが分りにくいかコメントして下さい!

masterqmasterq 2011/07/09 21:29 それぞれの関数に型が書いてあると、素人の僕にはわかりやすいかもしれないです。。

tt 2012/07/19 02:41 instance (Show a) => Show (Monadic a) where
show x = show $ run x 0

nil' :: Monadic (List a)
nil' = return Nil

cons' :: a -> Monadic (List a) -> Monadic (List a)
cons' x xs' = xs' >>= \xs -> cons0 x xs

を付け足すと、よりカッコよくなると思います。

ghci> (cons' "c" (cons' "b" (cons' "a" nil')))
→ (Cons "c" (Cons "b" (Cons "a" Nil)),3)

ただ、

> 要素の数を覚えさせておきたいとしましょう。もちろん、数えれば分りますが、数えなくても一瞬で分るようにしたいのです。

run を走らせるときに数えるので、覚えているわけでも、一瞬で分かるわけでもないのでは?

uehajuehaj 2013/11/14 09:22 ステップバイステップで受け渡したり、進んで行ったりするのではなく
合成された単一の純粋関数が出来上がってるだけなんですね。

驚愕。

図があるといいと思いますが、自分で取り組んでみたいとおもっています。

hogehoge 2015/10/16 16:45 このページを読んでもさっぱり分からなかった人へ

私はStateモナドについて解説した他のページを色々読み漁ってみたもののどれもさっぱり分からず、このページを最後の頼みとして気合いを入れ3度読み返して見ましたが、それでもさっっっぱり分かりませんでした。

そこで以下のようにトレースしてみたところようやくおぼろげな理解に至りましたので、良かったら参考にしてください。

-- import 文はファイルの冒頭に置く
import Debug.Trace

-- >>= の代わり
bind :: (Show a, Show b) => Monadic a -> (a -> Monadic b) -> Monadic b
Monadic f `bind` g = Monadic $ \cnt0 -> let (result1, cnt1) = f cnt0
Monadic h = g result1
(result2, cnt2) = h cnt1
in trace ("cnt0: " ++ show cnt0 ++ "\n" ++
"(result1, cnt1): " ++ show (result1, cnt1) ++ "\n" ++
"(result2, cnt2): " ++ show (result2, cnt2) ++ "\n")
(result2, cnt2)

-- return の代わり
ret :: Show a => a -> Monadic a
ret x = Monadic $ \cnt -> trace ("(x, cnt): " ++ show (x, cnt) ++ "\n") (x, cnt)

-- triple の代わり
triple' :: Monadic (List String)
triple' = cons0 "a" Nil `bind` (\a ->
cons0 "b" a `bind` (\b ->
cons0 "c" b `bind` (\c ->
ret c)))

-- 以下は実行結果
*Main> run triple' 0
(x, cnt): (Cons "c" (Cons "b" (Cons "a" Nil)),3)

cnt0: 2
(result1, cnt1): (Cons "c" (Cons "b" (Cons "a" Nil)),3)
(result2, cnt2): (Cons "c" (Cons "b" (Cons "a" Nil)),3)

cnt0: 1
(result1, cnt1): (Cons "b" (Cons "a" Nil),2)
(result2, cnt2): (Cons "c" (Cons "b" (Cons "a" Nil)),3)

cnt0: 0
(result1, cnt1): (Cons "a" Nil,1)
(result2, cnt2): (Cons "c" (Cons "b" (Cons "a" Nil)),3)

(Cons "c" (Cons "b" (Cons "a" Nil)),3)

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証