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

学習の素材は、
[すごいHaskellたのしく学ぼう!](http://www.amazon.co.jp/すごいHaskellたのしく学ぼう-Miran-Lipovača/dp/4274068854)

---
## モナドを作る動機
教材には、次のようにある。

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

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

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

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

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

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

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

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

## Functor のインスタンスにする

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

このような形になる。

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

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

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

### `(>>=)` を実装する
次の法則を手掛かりに、`join` に相当する関数を実装する。

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

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

その実装は

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

となっている。

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

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

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

![Group.png](https://qiita-image-store.s3.amazonaws.com/0/37895/ec80391e-ab91-38b1-60ee-4433bd15c58d.png)

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

```hs
-- スターバックスで注文する飲み物
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` 関数として定義できれば良い。通常のリストの操作に加えて、入れ子の中の確率付きリストが持つ確率に、外の確率を掛けていくような操作を足せば良い。

```hs
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` インスタンスの与え方としてはコンパクトに定義することができるようになる。

```hs
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)]
```


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