LoginSignup
9
10

More than 5 years have passed since last update.

@gomi_ningen

Maybeモナド と Listモナド

Last updated at Posted at 2015-05-04

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

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 とよんでいます。

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

Maybeモナド

まずはbind操作になれよう

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

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

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 を以下を埋める形で自分で実装してみてください。

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的なもの

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

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

解答例

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 型クラスの定義を見てみましょう

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 のインスタンスにせよ

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

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

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

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

解答例：

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)

問6. List を Monad/Applicative/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
-- 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に入力して試そう

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

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. 以下のコードをghciで試してみてください

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. 以下のコードをghciで試してみてください

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
9
10