Maybeモナド と Listモナド

> [すごいHaskell たのしく学ぼう　13章 「モナドがいっぱい」](http://www.amazon.co.jp/dp/4274068854)の部分の読書会用に作成した資料を公開します。演習問題や周辺の話題に軽くそれている部分があります。間違い等ありましたらご指摘いただけると幸いです。


# 13. モナドがいっぱい

FunctorやApplicativeを導入した動機のひとつとして以下のようなものがあると思います。

* Functor を導入した動機
  * a -> b 型の関数を f a -> f b の関数にしたい (fmap操作が欲しい)
* Applicative を導入した動機
  * f (a -> b) 型を f a -> f b 型の関数にしたい (<*>操作が欲しい)

Functor/Applicativeを導入した動機に以上のようなものがあったのと同じくMonadを導入する動機として次のようなものがあります

> 「普通の値 a を取って文脈付きの値を返す関数 (a -> m b) に、文脈付きの値 m a を渡したい」

Haskellではこの操作を行う関数として `>>=` という記号を用い、 `bind` とよんでいます。

```haskell
(>==) :: (Monad m) => m a => (a -> m b) -> m b
```


## Maybeモナド

まずはbind操作になれよう

### 問1. `(>>=)` のふるまいを理解しよう

以下のコードをghciで試してみてください

```haskell
Prelude> Just 3 >>= (\x -> Just x)
Just 3
Prelude> -- 右辺の Just は (\x -> Just x) と等価だということがわかる
Prelude> Just 3 >>= Just
Just 3
Prelude> Just 3 >>= (\x -> Just (2 * x))
Just 6
Prelude> Just 3 >>= (\x -> Just x)
Just 3
Prelude> -- bindを連ねることも出来る（関数の型から明らかではあるが）
Prelude> Just 3 >>= (\x -> Just (2 * x)) >>= (\y -> Just (10 + y))
Just 16
Prelude> -- 計算途中で Nothing が存在すると以降は Nothing が伝播する
Prelude> Nothing >>= (\x -> Just (2 * x))
Nothing
Prelude> Nothing >>= Just
Nothing
Prelude> Just 3 >>= (\x -> Nothing) >>= (\x -> Just x)
Nothing
```

### 問2 Maybe の `>>=` 関数を実装してみよう

Maybeの `(>>=)` 関数そっくりな振る舞いをするデータ型 `Option` の関数 `bind` を以下を埋める形で自分で実装してみてください。


```haskell
data Option a = Some a | None deriving(Show, Read, Ord, Eq)

bind :: Option a -> (a -> Option b) -> Option b
bind -- question --
bind -- question --
```

### Java/ScalaでのMaybe的なもの

```haskell
Just "java" >>= \x -> Just(x ++ "script")
Just "java" >>= \x -> Nothing
```

上のコードはJavaの以下のコードと計算結果が同じになる

```java
// Optional[javascirpt]が得られる
Optional.empty()
        .flatMap(x -> Optional.of(x + "script"));

// Optional.emptyが得られる
Optional.of("java")
        .flatMap(x -> Optional.of(x + "script"));
```

scalaだと以下のような具合

```scala
scala> Some("java").flatMap(x => Some(x + "script"))
res5: Option[String] = Some(javascript)

scala> (None:Option[String]).flatMap(x => Some(x + "script"))
res6: Option[String] = None
```

### 問3 OptionをFunctor/Applicativeのインスタンスにせよ

解答例

```haskell
module Option where

import Control.Applicative

data Option a = Some a | None deriving (Show, Read, Ord, Eq)

bind :: Option a -> (a -> Option b) -> Option b
bind (Some a) f = f a
bind None     f = None

instance Functor Option where
    fmap _ None     = None
    fmap f (Some a) = Some (f a)

instance Applicative Option where
    pure x = Some x
    None   <*> _ = None
    Some f <*> x = fmap f x
```


## Monad 型クラス

Monad 型クラスの定義を見てみましょう

```haskell
class Monad m where
    return :: a -> m a

    (>>=) :: m a -> (a -> m b) -> m b

    (>>) :: m a -> m b -> m b
    x >> y = x >>= \_ -> y

    fail :: String -> m a
    fail msg = error msg
```

* return は Applicative の pure と同じで、単なる値を文脈付きの値に変換するもの
* I/Oを扱った際に単なる値をI/Oアクションに変換するために使っている
* Maybe の場合は存在する値に対して`Just`というラベリングをすればよい
* `>>=` は モナド値と、通常の値から文脈付きの値への関数をとって、適用値を返す関数

### 問4. 型コンストラクタ Option を Monad のインスタンスにせよ

```haskell
instance Monad Option where
--以下を埋めよ
--
--
--
--
```

### 問5. OptionをFunctor/Applicativeのインスタンスにせよ

ただし Option が Monad であることを利用して実装すること。以下のリンクや `Control.Monad.liftM`, `Control.Monad.ap` の実装を参考にすると良い。

* https://wiki.haskell.org/Functor-Applicative-Monad_Proposal
* https://hackage.haskell.org/package/base-4.6.0.1/docs/src/Control-Monad.html

```haskell
-- liftM/liftM2/apの実装
-- | Promote a function to a monad.
liftM   :: (Monad m) => (a1 -> r) -> m a1 -> m r
liftM f m1              = do { x1 <- m1; return (f x1) }

-- | Promote a function to a monad, scanning the monadic arguments from
-- left to right.  For example,
--
-- >    liftM2 (+) [0,1] [0,2] = [0,2,1,3]
-- >    liftM2 (+) (Just 1) Nothing = Nothing
--
liftM2  :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 f m1 m2          = do { x1 <- m1; x2 <- m2; return (f x1 x2) }

{- | In many situations, the 'liftM' operations can be replaced by uses of
'ap', which promotes function application. 

>       return f `ap` x1 `ap` ... `ap` xn

is equivalent to 

>       liftMn f x1 x2 ... xn

-}

ap                :: (Monad m) => m (a -> b) -> m a -> m b
ap                =  liftM2 id
```

解答例：

```haskell
module Option where

import Control.Monad
import Control.Applicative

data Option a = Some a | None deriving (Show, Read, Ord, Eq)

instance Monad Option where
    return x = Some x
    None   >>= f = None
    Some x >>= f = f x
    fail _ = None

instance Functor Option where
    fmap = liftM

instance Applicative Option where
    pure = return
    (<*>) = ap
```

このコードで `fmap` や `<*>` が正しく機能するか確かめよう

```haskell
Prelude> fmap (++ "abc") (Some "a")
Some "aabc"
Prelude> (++) <$> Some "a" <*> Some "b"
Some "ab"
```

## リストモナド

リスト（の型コンストラクタ）は答えが複数あるかもしれない計算（非決定計算）であるという文脈を持つモナドです。

```haskell
Prelude> [1, 2] >>= \x -> [2 * x]
[2,4]
Prelude> [1] >>= \x -> [x, x + 1]
[1,2,2,3]
```

Javaだと以下のコードと（計算結果が）同じになる

```java
Stream.of(1, 2)
        .flatMap(x -> Stream.of(2 * x))
        .collect(Collectors.toList()); //=> List(2,4)
Stream.of(1, 2)
        .flatMap(x -> Stream.of(x, x + 1))
        .collect(Collectors.toList()); //=> List(1,2,2,3)
```

scalaだと以下のコードと計算結果が同じになる

```scala
scala> List(1,2).flatMap(x => List(2 * x))
res17: List[Int] = List(2, 4)

scala> List(1,2).flatMap(x => List(x, x+1))
res18: List[Int] = List(1, 2, 2, 3)
```

### 問6. List を Monad/Applicative/Functor のインスタンスにしよう

以下のinstance Monad, Applicative, Functor の部分が不完全なので埋めてください

```haskell
module List where

import Control.Monad
import Control.Applicative

data List a = Nil | Cons a (List a) deriving (Show, Read, Ord, Eq)

cons :: a -> List a -> List a
cons x xs = Cons x xs

join' :: List a -> List a -> List a
join' Nil ys = ys
join' (Cons x xs) ys = Cons x (join' xs ys)

concat' :: List (List a) -> List a
concat' Nil = Nil
concat' (Cons x xs) = join' x (concat' xs)

map' :: (a -> b) -> List a -> List b
map' _ Nil = Nil
map' f (Cons x xs) = Cons (f x) (map' f xs)

instance Monad List where
-- Q6


instance Applicative List where
-- Q6


instance Functor List where
-- Q6


```

MonadのインスタンスにしたのにApplicativeのインスタンスにしていない場合ghciで読み込むとMonadの以下の警告がでることに注目したい

```
*List Control.Monad> :l List.hs
[1 of 1] Compiling List             ( List.hs, interpreted )

List.hs:23:10: Warning:
    ‘List’ is an instance of Monad but not Applicative - this will become an error in GHC 7.10, under the Applicative-Monad Proposal.
Ok, modules loaded: List.
```


## do記法

do記法はHaskellがモナドのために用意したシンタックス。複数のモナド値を糊付けできる。

### 問7. 以下のコードをREPLに入力して試そう

```haskell
Prelude> Just 30 >>= Just
Just 30
Prelude> :{
Prelude|   do
Prelude|       a <- Just 30
Prelude|       Just a
Prelude| :}
Just 30
Prelude> getLine >>= putStrLn
hoge
hoge
Prelude> :{
Prelude|   do
Prelude|     a <- getLine
Prelude|     putStrLn a
Prelude| :}
hoge
hoge
Prelude> -- do記法を使うと簡略になる事例
Prelude> Just 5 >>= (\x -> Just 10 >>= (\y -> Just (x + y)))
Just 15
Prelude> :{
Prelude|   do
Prelude|       x <- Just 5
Prelude|       y <- Just 10
Prelude|       return (x + y)
Prelude| :}
Just 15
```

* http://www.slideshare.net/tanakh/monad-tutorial

scalaでもfor-comprehensionなどという構文が用意されている

```scala
scala> for {
     |   x <- Some(5)
     |   y <- Some(10)
     | } yield x + y
res20: Option[Int] = Some(15)
```

## MonadPlus

Monoid則を満たすMonadは、MonadPlus型クラスのインスタンスにできる

```haskell
class Monad m => MonadPlus m where
    mzero :: m a
    mplus :: m a -> m a -> m a
```

### 問8. List を MonadPlus のインスタンスにしよう

List と 連結演算 は Monoid であるので、 MonadPlus のインスタンスにできる

```haskell
instance MonadPlus List where
    mzero = -- Q8
    mplus = -- Q8
```

### 問9. Monoid則を満たすことを確認してみてください

厳密なチェックではないですが、結合律と単位元の存在を適当な例で確認すれば雰囲気は掴めると思います。

```haskell
Prelude> -- 結合律
Prelude> (Cons "a" Nil  `mplus` Cons "b" Nil) `mplus` Cons "c" Nil
Cons "a" (Cons "b" (Cons "c" Nil))
Prelude> Cons "a" Nil  `mplus` (Cons "b" Nil `mplus` Cons "c" Nil)
Cons "a" (Cons "b" (Cons "c" Nil))
Prelude> 
Prelude> -- 単位元の存在
Prelude> mzero `mplus` Cons "a" Nil
Cons "a" Nil
Prelude> Cons "a" Nil `mplus` mzero
Cons "a" Nil
```

## リスト内包表記

### 問10. 以下のコードをghciで試してみてください

```haskell
Prelude> -- リスト内包表記
Prelude> [ (n, ch) | n <- [1,2], ch <- ['a','b'] ]
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]
Prelude> 
Prelude> -- do構文を用いた表記
Prelude> :{
Prelude|   do
Prelude|       n <- [1,2]
Prelude|       ch <- ['a','b']
Prelude|       return (n, ch)
Prelude| :}
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]
```

リスト内包表記におけるフィルターは以下のguard関数を利用して実現されている

```haskell
guard :: (MonadPlus m)  => Bool -> m()
guard True = return ()
guard False = mzero
```

### 問11. 以下のコードをghciで試してみてください

```haskell
Prelude> [ x | x <- [1..50], x > 40]
[41,42,43,44,45,46,47,48,49,50]
Prelude>
Prelude> :{
Prelude>   do
Prelude>       x <- [1..50]
Prelude>       guard (x > 40)
Prelude>       return x
Prelude> :}
[41,42,43,44,45,46,47,48,49,50]
```

リストとその連結演算はMonadPlusのインスタンスであり、guard関数に与えた条件を満たさない要素はmzero、つまり連結演算についての単位元に変換されるため、フィルターの挙動を実現することができる

## モナド則

モナドが満たさなければいけない行けない法則は以下の３つです

* 左恒等性：`return x >>= f` と `f x` が等価である
* 右恒等性：`m >>= return` と `m` が等価である
* 結合法則：`(m >>= f) >>= g` と `m >>= (\x -> f x >>= g)` が等価である