Skip to content

Instantly share code, notes, and snippets.

@yashigani

yashigani/main.md

Last active December 21, 2015 06:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save yashigani/6265745 to your computer and use it in GitHub Desktop.
Save yashigani/6265745 to your computer and use it in GitHub Desktop.
Download ZIP
すごいH本読書会 #12
Raw
main.md

13 モナドがいっぱい

おさらい

Functor

  • 文脈を持った値に関数を適用する

    • f aに(a -> b)を適用したい

  • r -> aからr -> bに

    fmap :: (Functor f) => (a -> b) -> f a -> f b

Applicative Functor

  • 文脈を持った値に文脈を持った関数を適用する

    (<*>) :: (Applicative f) => f (a -> b) -> f a -> f b

  • 通常の値を文脈に入れる

    • pureのこと

  • Applicative値は「文脈の追加された値」

    > (*) <$> Just 2 <*> Just 8
Just 16
> (++) <$> Just "exdeath" <*> Nothing
Nothing
> (-) <$> [3, 4] <*> [1, 2, 3]
[2, 1, 3, 3, 2, 1]

  • それぞれの文脈

    • Maybe -> 失敗するかもしれない
    • [a] -> 複数の答えがあり得る計算(非決定性計算)
    • IO a -> 副作用を共なう計算

Monad

  • Applicative値の自然な拡張(強い版) 「普通の値aをとって文脈付きの値を返す関数に，文脈付きの値m aを渡したい」

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

  • Monadは>>=をサポートするApplicative Functor

    • >>=は**バインド(bind)**と呼ぶ

Maybeを見てみる

Maybeは失敗するかもしれない計算

> Just (++ "&") <*> Just "yotsuba"
yotsuba&
> Nothing <*> Just "yanda"
Nothing
> (,) <$> Just "yotsuba" <*> Just "to-chan"
Just ("yotsuba", "to-chan")
> (,) <$> Just "yanda" <*> Nothing
Nothing

>>=をどう実装すればいいか

  • Applicative Functorでは一度解いてから適用した
  • 同じようにやってみる
applyMaybe :: Maybe a -> (a -> Maybe b) -> Maybe b
applyMaybe Nothing f = Nothing
applyMaybe (Just x) f = f x

使ってみる

> Just "yotsuba" `applyMaybe` \x -> Just (x ++ "&")
Just "yotsuba&"
> Nothing `applyMaybe` \x -> Just (x ++ "&")
Nothing

関数がNothingを返す場合は？

> Just "yotsuba" `applyMaybe` \x -> if x == "yanda" then Nothing else Just (x ++ "&")
Just "yotsuba&"
> Just "yanda" `applyMaybe` \x -> if x == "yanda" then Nothing else Just (x ++ "&")
Nothing

どこがすごいの？

  • Applicative Functorは普通の関数を文脈付きの値に適用できた
  • 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
  • Applicativeのインスタンスではない

Monadの関数

  • return
    • Applicativeでいうpure
    • IOで使ったよね？
  • >>=
    • バインド
    • Monad値(文脈付きの値)に「通常の値を取るがMonad値を返す関数」を適用する
  • >>
    • あとで
  • fail
    • パターンマッチに失敗したときにハンドリングするやつ
instance Monad Maybe where
    return x = Just x
    Nothing >>= f = Nothing
    Just x >>= f = f x
    fail _ = Nothing
> return "yotsuba" :: Maybe String
Just "yotsuba"
> Just "yotsuba" >>= \x -> Just (x ++ "&")
Just "yotsuba&"
> Nothing >>= \x -> Just (x ++ "&")
Nothing
  • パターンマッチを使わずにMaybeから値を取り出したように見える
  • 文脈は維持している(NothingのときはNothingになる)

綱渡り

>>=を繰り返し使ってMaybe a型の値を貸す複数の計算を扱う

まずは普通に作ってみる

> landLeft 2 (0, 0)
(2, 0)
> landRight 1 (1, 2)
(1, 3)
> landRight -1 (1, 2)
(1, 1)
> land Left 2 (landRight 1 (landLeft 1 (0, 0)))
> (3, 1)

途中で失敗してもスルーしてる

  • Maybeで包んでやる

    > landLeft 2 (0, 0)
Just (2,0)
> landLeft 10 (0, 3)
Nothing

  • 落ちるようになったけど，landLeft 1 (landRight 1 (0, 0))みたいに書けなくなった

  • >>=を使えばいいよ

    > landRight 1 (0, 0) >>= landLeft 2
Just (2, 1)
# Nothingを渡してみる
> Nothing >>= landLeft 2
Nothing
> return (0, 0) >>= landRight 2 >>= landLeft 2 >>= landRight 2
Just (2,4)

# さっきダメだった例を試す

> return (0, 0) >>= landLeft 1 >>= landRight 4 >>= landLeft (-1) >>= landRight (-2)
Nothing

  • MaybeをApplicative値としてだけ扱うだけではここまではできない Applicative FunctorではApplicative値どうしを深く相互作用できない．できるのはせいぜい通常の関数にApplicative Styleで引数を渡すくらい

  • ピエールの例は前の結果に依存している -> 前の結果を踏まえて今回の結果が検証される

ロープ上のバナナ

  • ピエールを滑らせる bananaの導入

    > return (0, 0) >>= landLeft 1 >>= banana >>= landRight 1
Nothing

  • 既定のMonad値を返す関数>>

    (>>) :: (Monad m) => m a -> m b -> m b
m >> n = m >>= \_ -> n

  • Maybeで使ってみる

    > Nothing >> Just 3
Nothing
> Just 3 >> Just 4
Just 4
> Just 3 >> Nothing
Nothing

  • bananaの代わりに使ってみる

    > return (0, 0) >>= landLeft 1 >> Nothing >>= landRight 1
Nothing

  • もしMonadがなかったら

    routine :: Maybe Pole
routine = case landLeft 1 (0, 0) of
    Nothing -> Nothing
    Just pole1 -> case landRight 4 pole1 of
        Nothing -> Nothing
        Just pole2 -> case landLeft 2 pole2 of
            Nothing -> Nothing
            Just pole3 -> landLeft 1 pole3

    oh...

do記法

  • IOで出てきたdoは他のMonadでも使える

    > Just 3 >>= (\x -> Just (show x ++ "!"))
Just "3!"
> Just 3 >>= (\x -> Just "!" >>= (\y -> Just (show x ++ y)))
Just "3!"

  • let x = 3; y = "!" in show x ++ yに似てる

  • >>=を使うほうはMonad値なので好きなところを失敗に置きかえられる

    > Nothing >>= (\x -> Just "!" >>= (\y -> Just (show x ++ y)))
Nothing
> Just 3 >>= (\x -> Nothing >>= (\y -> Just (show x ++ y)))
Nothing
> Just 3 >>= (\x -> Just "!" >>= (\y -> Nothing))
Nothing

  • letに似てる

  • スクリプト風に書いてみる

    foo :: Maybe String
foo = Just 3   >>= (\x ->
      Just "!" >>= (\y ->
      Just (show x ++ y)))

-- これはdo記法を使うとこう書ける

foo' :: Maybe String
foo' = do
    x <- Just 3
    y <- Just "!"
    Just (show x ++ y)

do自由自在

  • do式はlet行以外は全てMoad
  • 結果を取り出すには束縛する
  • 最後の行では使えない
    • 受けるべきラムダ式が無いから
> Just 9 >>= (\x -> Just (x > 8))
Just True

と

marySue :: Maybe Bool
marySue = do
    x <- Just 9
    Just (x > 8)

を比べると，最後の結果がdo式全体の結果になる仕組みがわかる

帰ってきたピエール

  • ピエールをdoで渡らせてみる

    routine :: Maybe Pole
routine = do
    start <- return (0, 0)
    first <- landLeft 2 start
    second <- landRight 2 first
    landLeft 1 second

  • 手続きっぽく見える！

    • 前の行の結果に依存した値の列が文脈と一緒に書いてあるだけ

  • バナナを踏ませたければ...

    routine :: Maybe Pole
routine = do
    start <- return (0, 0)
    first <- landLeft 2 start
    Nothing
    second <- landRight 2 first
    landLeft 1 second

  • 束縛せずにMonadを使うと，>>をつけたのと同じ結果になる

  • doを使うか>>=を使うかはお好きに！

パターンマッチと失敗

  • do式ではパターンマッチが使える

    justH :: Maybe Char
justH = do
    (x:xs) <- Just "hello"
    return x

  • 失敗したときどうなるの？

    • パターンマッチは失敗したら次のパターンを試す
    • letは複数のパターンを試せなかった -> 即座にエラー
    • doではfailが使われる
      • Maybeではfail _ = Nothingってなってる

リストモナド

  • Applicativeとしてのリストは非決定性計算を表す

    > (*) <$> [1, 2, 3] <*>[10, 100, 1000]
[10, 100, 1000, 20, 200, 2000, 30, 300, 3000]

  • Monadならもっとうまく書ける

    instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)
    fail _ = []

  • 使ってみる

    > [3, 4, 5] >>= \x -> [-x, x]
[-3, 3, -4, 4, -5, 5]

  • つまりこういうこと

    [3, 4, 5] >>= \x -> [-x, x]
concat (map (\x -> [-x, x]) [3, 4, 5])
concat [[-3, 3], [-4, 4], [-5, 5]]
[-3, 3, -4, 4, -5, 5]

  • 空リストのときは？

    > [] >>= \x -> ["bad", "mad", "red"]
[]
> [1, 2, 3] >>= \x -> []
[]

  • 連結させてみる

    > [1, 2] >>= \n -> ['a', 'b'] >>= \ch -> return (n, ch)
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]

  • do記法で

    listOfTuples :: [(Int, Char)]
listOfTuples = do
    n <- [1, 2]
    ch <- ['a', 'b']
    return (n, ch)

do記法とリスト内包表記

  • さっきのはリスト内包表記に似てる

    > [(n, ch) | n <- [1, 2], ch <- ['a', 'b']]
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]

  • 実はリストモナドのSyntax Suger

MonadPlusとguard関数

  • リスト内包表記ではfilterができる

    > [x | x <- [1..50], '7' `elem` show x]
[7, 17, 27, 37, 47]

  • guard関数とMonadPlus型クラス Monoidの性質をあわせ持つ型クラス

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

mzero = mempty mplus = mappend

  • リストはMonoidなのでMonadPlusのインスタンスにできる

    instance MonadPlus [] where
    mzero = []
    mplus = (++)

  • 一方guardはこんな感じ

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

    Trueなら()を最小の文脈に入れ，Falseなら失敗を作る

    > guard (5 > 2) :: Maybe ()
Just ()
> guard (1 > 2) :: Maybe ()
Nothing
> guard (5 > 2) :: [()]
[()]
> guard (1 > 2) :: [()]
[]

  • リスト内包表記っぽく

    > [1..50] >>= (\x -> guard ('7' `elem` show x) >> return x)
[7, 17, 27, 37, 47]

  • guardを>>につないでみる

    > guard (5 > 2) >> return "cool" :: [String]
["cool"]
> guard (1 > 2) >> return "cool" :: [String]
[]

  • doで書き直す

    sevensOnly :: [Int]
sevensOnly = do
    x <- [1..50]
    guard ('7' `elem` show x)
    return x

モナド則

左恒等性

  • returnしたものを>>=した場合は，元の値に関数を適用した場合と同じ

    > return 3 >>= (\x -> Just (x + 100000))
Just 100003
> (\x -> Just (x + 100000)) 3
Just 100003
> return "WoM" >>= (\x -> [x, x, x])
["WoM", "WoM", "WoM"]
> (\x -> [x, x, x])
"WoM" ["WoM", "WoM", "WoM"]

右恒等性

  • >>=を使ってMonad値をreturnに食わせても何も起こらない

    > Just "move on up" >>= return
Just "move on up"
> [1, 2, 3, 4] >>= return
[1, 2, 3, 4]
> putStrLn "Wah!" >>= return
Wah!

結合法則

  • >>=の連鎖があるときに，どの順序で評価しても結果は同じ

    • つまり(m >>= f) >>= gとm >>= (\x -> f x >>= g)が等価

  • 以下の式は等価

    • 評価される順番は関係無い
    > return (0, 0) >>= landRight 2 >>= landLeft 2 >>= landRight 2
Just (2, 4)
> return (0, 0) >>= (\x -> landRight 2 x >>= (\y -> landLeft 2 y >>= (\z -> landRight 2 z)))
Just (2, 4)

  • 関数合成を思い出してみる

    (.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = (\x -> f (g x))

  • fとgにMonad関数を渡すことを考える

    • >>=使えばいける
    (<=<) :: (Monad m) => (b -> m c) -> (a -> m b) -> (a -> m c)
f <=< g = (\x -> g x >>= f)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment