13. モナドがいっぱい

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

モナド：「普通の値 a を取っ文脈付きの値を返す関数 (a -> m b) に、文脈付きの値 m a を渡したい」という願いをかなえるもの。この関数 >>= は bind とよばれている。

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

Maybeモナド

まずはbind操作になれよう

問1. 以下のコードをREPLに入力して試せ

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.1 以上で確認したMaybeの挙動をOptionとして自分で実装せよ

Maybeそっくりな振る舞いをするデータ型 Option を以下を埋める形で自分で実装してください。

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

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

余談

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

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

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

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

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

問2.2 Option型コンストラクタをFunctorのインスタンスにせよ

問2.3 Option型コンストラクタをApplicativeのインスタンスにせよ

Monad 型クラス

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

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というラベリングをすればよい
bind はモナド値と、通常の値から文脈付きの値への関数をとって、適用値を返す関数

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

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

問3.2 型コンストラクタOptionをFunctorのインスタンスにせよ

問3.3 型コンストラクタOptionをApplicativeのインスタンスにせよ

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

-- Control.Monad.hs
-- | 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

解答例：

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 や <*> が正しく機能するか確かめよう

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

リストモナド

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

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

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> 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)

問4. 以下のデータ構造 List を Monad のインスタンスにせよ

問5. 以下のデータ構造 List を Applicative のインスタンスにせよ

問6. 以下のデータ構造 List を Functor のインスタンスにせよ

以下のinstance Monad ~~, Applicative, Functor の部分が不完全なので埋めよ

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
-- Q4


instance Applicative List where
-- Q5


instance Monad Functor where
-- Q6

問4だけ終わったあとに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に入力して試せ

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

MonadPlus

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

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

問8. List を MonadPlus のインスタンスにせよ

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

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

問9. Monoid則を満たすことを確認せよ

結合律と単位元の存在を適当な例で確認すれば良い

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. 以下のコードをREPLで試せ

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関数を利用して実現されている

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

問11. 以下のコードをREPLで試せ

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) が等価である

53ningen/13_monad.md