アプリカティブファンクタの拡張にあたるモナドを探る

あるアプリカティブファンクタが与えられたときその拡張にあたるモナドを探る話です。
「モナドとは」、「アプリカティブとは」、「それらの違いは」という話はしません。ごめんね。

# アプリカティブの基本関数

まずはアプリカティブの話に必要な関数の整理をしておきます。

（以下、型に現れる `f` はアプリカティブを、`m` はモナドを表すことにしていちいち `Applicative f` と `Monad m` は書きません。
式の方にもよく関数としての `f` も現れて混乱しますね。なれるしかないんでしょうか）

Haskell でアプリカティブを扱うときには基本的に2つの関数

```
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
```

を使います。

しかしこれからの話には `(<*>)` よりも `liftA2` という関数を使う方が簡単なことが多いのでその `liftA2` を紹介しましょう。
`(<*>)` を使っての `liftA2` の 定義は以下のとおりです。

```
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 f x y = f <$> x <*> y

{- f <$> x は fmap f x -}
```

逆に `(<*>)` は `liftA2` を使って書けます。

```
(<*>) :: f (a -> b) -> f a -> f b
(<*>) = liftA2 id
```

# モナドはアプリカティブ

すべてのモナドは次の定義によってアプリカティブファンクタになることが知られています。

```
pure :: a -> m a
pure = return

(<*>) :: m (a -> b) -> m a -> m b
m1 <*> m2 = ap m1 m2

{- ap m1 m2 とは do { f <- m1; x <- m2; return (f x) } -} 

liftA2 :: (a -> b -> c) -> m a -> m b -> m c
liftA2 f m1 m2 = liftM2 f m1 m2

{- liftM2 f m1 m2 とは do { x <- m1; y <- m2; return (f x y) } -} 
```

`liftM2` を `join` と `fmap` を使った式に書き直しましょう。

```
liftM2 f m1 m2
  = do { x <- m1; y <- m2; return (f x y) }
  = m1 >>= (\x -> m2 >>= (\y -> return (f x y)))
    {-  ここは頑張って join と fmap を使った式に変形していく -}
  = join (fmap (\x -> fmap (f x) m2) m1)
```

# アプリカティブの拡張としてのモナド

やっと準備が終わりました。
与えられたアプリカティブがモナドに拡張できるかの話に入ります。

以下で登場するモナドの関数 join については前の記事 [join と (>>=) と、時々、fmap](http://qiita.com/1to100pen/items/3ac5864b648b1d7b81ae) で紹介しています。

あるアプリカティブがモナドに拡張できるとはあるモナドがあってそのモナドの `return` と `join` を使って定義した

```
pure = return
liftA2 f m1 m2 = liftM2 f m1 m2 = join (fmap (\x -> fmap (f x) m2) m1)
```

がアプリカティブの `pure` と `liftA2` と一致するということとします。
この等式の左右を逆に見れば

```
return == pure
join (fmap (\x -> fmap (f x) m2) m1) == liftA2 f m1 m2
```

拡張にあたるモナドがあるとすればそのモナドの `return` については `pure` で決まりですからあとは

```
join (fmap (\x -> fmap (f x) m2) m1) == liftA2 f m1 m2
```

を満たす `join` を決定できればモナドを決定できたことになります。

# Maybeアプリカティブの拡張としてのモナドを探る

試しに Maybeアプリカティブファンクタの拡張にあたるモナドがあるか探ってみましょう。
（Maybeモナドに決まっているだろう？そのとおりなんですがここは知らない振りで）

Maybeアプリカティブファンクタの `pure` と `liftA2` は以下のとおりです。

```
pure :: a -> Mabye a
pure x = Just x

liftA2 :: (a -> b -> c) -> Mabye a -> Mabye b -> Mabye c
liftA2 f (Just x) (Just y) = Just (f x y)
liftA2 f _ _ = Nothing
```

ですので拡張にあたるモナドがあるとすれば以下の等式を満たす必要があります。

```
return x == Just x

join (fmap (\z -> fmap (f z) (Just y)) (Just x)) == Just (f x y) -- (1)
join (fmap (\z -> fmap (f z) Nothing) (Just x)) == Nothing -- (2)
join (fmap (\z -> fmap (f z) (Just y)) Nothing) == Nothing -- (3)
join (fmap (\z -> fmap (f z) Nothing) Nothing) == Nothing -- (4)
```

ここで (1) の左辺を Maybe の fmap を使って変形していくと

```
join (fmap (\z -> fmap (f z) (Just y)) (Just x))
  = join (fmap (\z -> Just (f z y)) (Just x))
  = join (Just (Just (f x y)))
```

となります。(2),(3),(4) についても同様に計算して整理してまとめると

```
return x == Just x

join (Just (Just (f x y))) == Just (f x y)
join (Just Nothing) == Nothing
join Nothing == Nothing
```

ここで関数 `f` は任意の2引数関数でよいので `f` が特に関数

```
f x y = x
```
の場合を考えると（注： この関数は `const` という名前で知られている関数です）

```
return x == Just x

join (Just (Just x)) == Just x
join (Just Nothing) == Nothing
join Nothing == Nothing
```

となります。これは Maybeモナドの `return` と `join` そのものです。
実際 Maybeモナドは Maybeアプリカティブでもあります。

ということで

**Maybeアプリカティブファンクタの拡張にあたるモナドは唯一存在して、それは Maybeモナドである**

ということがわかりました。

多分次回 ZipListアプリカティブの拡張のモナドの話へと続きます。

---

May Monad be with you