モナドを自作する時の基本的な進め方 #Haskell

モナドを作る動機

教材には、次のようにある。

普通、モナドは作りたいと思って作るものではありません。むしろ、とある問題のある側面をモデル化した型を作り、後からその型が文脈付きの値を表現していてモナドのように振る舞うとわかった場合に、Monad インスタンスを与える場合が多いです。

個人的には、いくらHaskellでオリジナルのモナドを作れるとはいえ、文脈をデザインすることなんてできるの（そんなスキルあるの）だろうか・・と思っていたので、このように、モナドは発見的に見つかるものなのだ、ということがあらかじめわかっていれば安心である（笑）。

確率付きリスト`[(3, 1 % 2), (5, 1 % 4), (9, 1 % 4)]`

リストは非決定な値を表現している。例えば [3, 5, 9] は どの値を取るか決めかねている非決定的整数である と解釈できる。もし、この中の各要素が選ばれる可能性がそれぞれ異なっているとしたら、どう表したら良いか。一つは、このようにすることが考えられる。

[(3, 50%), (5, 25%), (9, 25%)]

Haskell の文法に合わせて書くと、このようになる。

import Data.Ratio
[(3, 1 % 2), (5, 1 % 4), (9, 1 % 4)]

これは、リストに対して何か手を加えたものなので、何らかの文脈付き値を表している と言えそうである。モナドになるかもしれないので、newtype で包んで見る。

newtype Prob a = Prob { getProb :: [(a, Rational)] } deriving (Show)

Functor のインスタンスにする

instance Functor Prob where
    fmap f (Prob xs) = Prob $ map (\(x, p) -> (f x, p)) xs

このような形になる。

*Main Data.Ratio> fmap (+2) (Prob [(3, 0.5), (4, 0.5)])
Prob {getProb = [(5,1 % 2),(6,1 % 2)]}

Monad のインスタンスにする

`return` を実装する

return はデフォルトの、最小限の文脈をもってこないといけない。リストに何かしらの文脈を付け加えたものなので、リストの最小限の文脈 単一要素のリスト と、一つしか要素がない場合の確率 1 を返すようにする。

return x = [(x, 1 % 1)]

`(>>=)` を実装する

次の法則を手掛かりに、join に相当する関数を実装する。

m >>= f = join (fmap f m)

ちなみに、join 関数とは、入れ子のモナドを平らにする関数であり、例えば join (Just (Just 8)) は Just 8 というように平らになる。

その実装は

join              :: (Monad m) => m (m a) -> m a
join x            =  x >>= id

となっている。

実際は(>>=) を使ってモナド値に id を適用している。今は (>>=) も join も実装できていないので、今回は(>>=) について新しい関数を使って(ここでは flatten 関数と命名 )定義することにする。

入れ子のモナド値をどのように平らにするか、という方針について、次の例で考えてみる。

Aさんは１日一回カフェに行き、飲み物を頼む
スタバには 3 / 4 の確率で、上島珈琲店には 1 /4 の確率で足を運んでいる
頼む飲み物はコーヒーかカフェラテのどちらかで、頼む頻度は同じ
前日、翌日飲んだものの影響は受けない
このとき、スタバ、上島珈琲店コーヒー、カフェラテを頼む確率はそれぞれいくつになるか。

型 Prob を使うと、次のように表せる。

-- スターバックスで注文する飲み物
Prob [("starbacks coffee", 1%2), ("starbacks late", 1%2)]

-- 上島珈琲店で注文する飲み物
Prob [("ueshima coffee", 1%2), ("ueshima late", 1%2)] 

-- 訪れる確率も考慮すると、入れ子のモナドができる
Prob [(Prob [("starbacks coffee", 1%2), ("starbacks late", 1%2)], 3%4), (Prob [("ueshima coffee", 1%2), ("ueshima late", 1%2)], 1%4)]

-- モナドを平らにした時の期待値
Prob [("starbacks coffee",3 % 8),("starbacks late",3 % 8),("ueshima coffee",1 % 8),("ueshima late",1 % 8)]

ここで、モナドを平らにするやり方をflatten 関数として定義できれば良い。通常のリストの操作に加えて、入れ子の中の確率付きリストが持つ確率に、外の確率を掛けていくような操作を足せば良い。

flatten :: Prob (Prob a) -> Prob a
flatten (Prob xs) = Prob $ concat $ map multAll xs
    where
        multAll (Prob innerxs, p) = map (\(x, r) -> (x, r * p)) innerxs

すると、Monad インスタンスの与え方としてはコンパクトに定義することができるようになる。

instance Monad Prob where
    return x    = Prob [(x, 1 % 1)]
    m >>= f     = flatten (fmap f m)
    fail _      = Prob []

これで join 関数も使えるようになったので試してみる。

*Main> getProb $ join (Prob [(Prob [("starbacks coffee", 1%2), ("starbacks late", 1%2)], 3%4), (Prob [("ueshima coffee", 1%2), ("ueshima late", 1%2)], 1%4)])

[("starbacks coffee",3 % 8),("starbacks late",3 % 8),("ueshima coffee",1 % 8),("ueshima late",1 % 8)]

バインドしてみる

join の次はバインド(>>=)の例として、組み合わせ確率を考える。

スタバの袋と上島珈琲の袋がある
スタバの袋には、1/3 の確率でコーヒーが、 2/3 の確率でカフェラテが入っている
上島珈琲の袋には、3/4 の確率でコーヒーが、 1/4 の確率でカフェラテが入っている
２つの袋から一つずつ、無作為に飲み物を取った場合の組み合わせ確率はどうなるか

*Main > getProb $ Prob [("starbacks coffee", 1%3), ("starbacks late", 2%3)] >>= \x -> (Prob [("ueshima coffee", 3%4), ("ueshima late", 1%4)] >>= \y -> return [x, y])

[(["starbacks coffee","ueshima coffee"],1 % 4),(["starbacks coffee","ueshima late"],1 % 12),(["starbacks late","ueshima coffee"],1 % 2),(["starbacks late","ueshima late"],1 % 6)]

いい感じにできた。ところで今回作成した「確率付き非決定性計算」モナドはモナド則を満たしているが、その確認は割愛する。

モナドを自作する時の基本的な進め方