2仮説2モナドとは言語内DSLのフレームワークという説明が一番分かり易い3
お品書き
■統一理論と大統一理論
■コンテナの力の階層■内包表記4 5 Q)抽象の壁を突破するにはどうすればいいのか？ A)まず具体例を見てから抽象化していくしかない6
Parser
■データ定義data Parser a = Parser (String -> [(a,String)]) ■ Parserを生成する関数pwrap :: a -> Parser a pwrap v   = Parser $ \inp -> [(v,inp)] ■ Parserを合成する関数pbind :: Parser a -> (a -> Parser b) -> Parser b pbind p f = ... ■利用例string :: String -> Parser String string []    = pwrap [] string (x:xs) = char x string xs      'pbind' \vs -> pwrap (v:vs) 11 IO ■データ定義data IO a = IO (World -> (a, World))注：IOは命令ではなく命令書。すなわちオブジェクト！ ■ IOを生成する関数iwrap :: a -> IO a iwrap v   = IO $ \world -> (v, world) ■ IOを合成する関数ibind :: IO a -> (a -> IO b) -> IO b ibind i f = ... ■利用例echoChar :: IO () echoChar = getChar 'ibind' \c -> putChar c ■あるいはechoChar = getChar 'ibind' putChar 12
■ ParserとIOには共通点はないか？ ■データ定義data Parser a = Parser (String -> [(a,String)]) data IO a     = IO     (World  ->  (a, World)) ■生成する関数pwrap :: a -> Parser a iwrap :: a -> IO a ■合成する関数ibind :: IO a     -> (a -> IO b)     -> IO b pbind :: Parser a -> (a -> Parser b) -> Parser b ■どちらも状態を表している！ →型クラスで抽象化13
状態系
■状態を表すクラスclass Stateful m where swrap :: a -> m a sbind :: m a -> (a -> m b) -> m b ■インスタンスinstance Stateful Parser where swrap = pwrap sbind = pbind instance Stateful IO where swrap = iwrap sbind = ibind 14
¤構文糖衣doを導入する
swrap (f v1 v2 .. vn) ◾doで書き直すstring []    = swrap [] string (x:xs) = do v  <- char x VS <- string xs swrap (v:vs) echoChar      = do c <- getChar putChar c ■命令型言語の逐次実行を再発明しちゃった！ 15
¤状態系の中身はsbindで合成された関数■パターンマッチで関数を取り出して、引数(初期値)を与えないと走らない■ runParser runParser :: Parser a -> String -> (a, String) runParser (Parser p) xs = p xs ◾ dataとgetterを同時に定義data Parser a = Parser { runParser :: String -> (a, String) ~
■ runlO
runIO :: IO a -> World -> (a, World) runIO (IO io) world = io world ■ IOは抽象データ型で構成子IOは公開されてない■パターンマッチできないので関数を取り出せない■ランタイムがrunIO  mainを実行16
Maybe
■データ定義data Maybe a = Nothing | Just a ■ Nothingは失敗■ Just aは成功■連想Listの検索lookup :: Eq a => a -> [(a, b)] -> Maybe b lookup 0 [(1,'a')] → Nothing lookup 1 [(1,'a')] → Just 'a'
18

子供をキーとして検索すると母親が出てくるDB ■おばあちゃんを探すコードcase lookup me db of Nothing  -> Nothing Just mom -> case lookup mom db of Nothing   -> Nothing Just gmom -> Just gmom ■どうにかならないの？
19
MaybeとBool ■ BoolのTrueに値を持たせたのがMaybe True data Bool    = False   | data Maybe a = Nothing | Just a ■ Boolの連鎖x > 0 && x < 100 ■ Maybeも連鎖にできないか？ lookup ... ??? lookup ...
20
Maybeの演算子
■ Maybeを生成する関数mwrap :: a -> Maybe a mwrap v  = Just v ■ Maybeを合成する関数mbind :: Maybe a -> (a -> Maybe b) -> Maybe b mbind Nothing  _ = Nothing mbind (Just x) f = f x 21
■ case版(再掲) case lookup me db of Nothing  -> Nothing Just mom -> case lookup mom db of Nothing   -> Nothing Just gmom -> Just gmom ■合成版lookup me  db 'mbind' \mom -> lookup mom db 'mbind' \gmom -> mwrap gmam
22

■合成版(再掲) lookup me  db 'mbind' \mom -> lookup mom db 'mbind' \gmom -> mwrap gmam ■あるいは単にlookup me  db 'mbind' \mom -> lookup mom db ■もうちょっと奇麗にlookup' :: Eq a => [(a, b)] -> a -> Maybe b lookup’ = flip lookup lookup’db me ’mbind’ lookup’db ■あまり意味がないけどmwrap me 23 List ■データ定義data [] a = [] | a : [a] ■型表記の統一data [] a = [] | a : [] a ■構成子を前にdata [] a = [] | (:) a ([] a) ■記号を単語にdata List a = Nil | Cons a (List a)
■データ定義data Maybe a = Nothing | Just a data List  a = Nil Cons a (List a) ■ Nilも失敗を表現していると考えられないか？ ■ Maybeは、失敗と一つの成功■ List     は、失敗と複数の成功■もっと抽象化して■ Maybeは、答えが0個か1個■ List     は、答えが0個以上■ Maybeが合成できるなら、 Listも合成できるのでは？
25

■ 0か1のかけ算と考えられるNothing >>= \x -> Nothing >>= \y -> return (x,y) → Nothing Nothing >>= \x -> Just 2 >>= \y -> return (x,y) → Nothing Just 1 >>= \x -> Nothing >>= \y -> return (x,y) → Nothing Just 1 >>= \x -> Just 2 >>= \y -> return (x,y) → Just (1,2)
26

■要素が0個か1個ならMaybeと同じはず[] >>= \x -> [] >>= \y -> return (x,y) → [ ] [] >>= \x -> [2] >>= \y -> return (x,y) → [ ] [1] >>= \x -> [] >>= \y -> return (x,y) → [ ] [1] >>= \x -> [2] >>= \y -> return (x,y) → [(1,2)] ■要素が複数の場合は？ →決めの問題[1,2] >>= \x -> [3,4,5] >>= \y -> return (x,y) → ??? ■かけ算だから組み合わせにする→ [(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)] ■実際zipを取る流儀もある
27

■失敗が含まれることを表すクラスclass Failable m where fwrap :: a -> m a fbind :: m a -> (a -> m b) -> m b ■インスタンスinstance Failable Maybe where fwrap = mwrap fbind = mbind instance Failable List where fwrap = lwrap fbind = lbind ■クイズ) IwrapとIbindの実装を考えてみよう
28

■木の探索を考えるdata Tree a = Leaf | Node (Tree a) a (Tree a) ■探索木ではない■右と左のどちらに答えがあるか分からない■答えは複数あるかもしれない■ Haskellなら全探索するように書くsearch :: Eq a => a -> Tree a -> [a] search _ Leaf = [] search x (Node l v r) x == v    = search x l ++ [v] ++ search x r otherwise = search x l ++ search x r ■実行してみるsearch 1 $ Node (Node Leaf 1 Leaf) 2 (Node Leaf 1 Leaf) → [1,1] 29
■失敗系で抽象化するsearch :: (Eq a, Failable m, Alternative m) => a -> Tree a -> m a search _ Leaf = empty search x (Node l v r) | x == v    = search x l <|> fwrap v <|> search x r | otherwise = search x l <|> search x r ■動かしてみるsearch 1先ほどの木:: [Int] → [1,1] search 1先ほどの木:: Maybe Int → Just 1
30
33
■中身が一つのコンテナdata Ｍａ = ... ■コンテナを生成wrap :: a -> m a wrap a = ... ■コンテナを合成bind :: m a -> (a -> m b) -> m b bind m f = ...
34

■プログラム可能なコンテナのクラスclass Programmable m where wrap :: a -> m a bind :: m a -> (a -> m b) -> m b
instance Programmable Parser where wrap = pwrap bind = pbind instance Programmable IO where wrap = iwrap
instance Programmable Maybe where wrap = mwrap bind = mbind instance Programmable List where wrap = lwrap bind = lbind 35
■失敗系でもdoが使えるdo x <- [1..5] y <- [ 2 . . 5 ] return (x,y) makePerson :: Int -> Maybe Person makePerson idnt = do name <- lookup idnt nameDB age  <- lookup idnt ageDB return $ Person name age ■注）makePersonは後述のApplicativeスタイルの方がよい■他の利点は後述
36

■ DSL (Domain Specific Language) ■文脈とも言われる■ Parser ■パーサー ■ IO ■副作用の表現■ Maybe ■失敗するかもしれない計算■ List ■答えが0個以上の計算■分岐する世界=非決定性
37

コンテナの力の階層
この三つがあれば、計算可能なすべてのアルゴリズムを実現できる41
まずmapより始めよ
■だれでも分かるmap map (+1) [1,2,3,4] → [ 2 , 3 , 4 , 5 ] ■二項演算子にしてみる(+1) 'map' [1,2,3,4] → [ 2 , 3 , 4 , 5 ] ◾mapを一般化した<$>という演算子を考える(+1) <$> [1,2,3,4] → [ 2 , 3 , 4 , 5 ] (+1) <$> Just 1 → Just 2
42

■ <$>を持つコンテナのクラスclass Mappable m where (<$>) :: (a -> b) -> m a -> m b ■インスタンスclass Mappable List where ( <$> )  =  map class Mappable Maybe where ( <$> )   =  mmap ■クイズ) mmapの実装を考えてみよう
43

■ <$>の型(<$>) :: (a -> b) -> m a -> m b ■fへ適用f :: a -> b (f <$>) :: m a -> m b ◾<$>は関数をDSL (文脈)用に変えている！ ■ DSLへ持ち上げる(lift)するという◾ｍというDSLを作る
44
純粋な関数をDSLに入れろ■二引数の関数を考えるf :: a -> b -> c ■ ->は右結合f :: a -> (b -> c) ■ <$>でDSLに持ち上げると(f <$>) :: m a -> m (b -> c) ■ DSLに関数が入る(+) <$> [1,2,3,4] → [(1+),(2+),(3+),(4+)] ■ DSLの中でも関数適用したい！
45

■ DSLの中で関数適用する演算子<*>の型は？ m (a -> b) -> m a -> m b ■使ってみる(+) <$> Just 1 <*> Just 2 → Just 3 (+) <$> [1,2] <*> [3,4] → [ 4 , 5 , 6 ] ■心眼で<$>と<*>を消せ■単なる関数適用に見える！ (+) (Just 1) (Just 2) (+) [1,2] [3,4]
46

■ <*>を持つコンテナのクラスclass Mappable m => Sequential m where return :: a -> m a (<*>) :: m (a -> b) -> m a -> m b
■ return
■今までのwrapのこと■ returnは本当はプログラム可能コンテナのメソッド■逐次コンテナの本当のメソッドはpure ■しかしpureとreturnを同一視しても問題ない■ここにreturnが入る理由は次のスライドで分かる
47

■逐次のdo
string :: String -> Parser String string []    = wrap [] string (x:xs) = do v  <- char x VS <- string xs wrap (v:vs) -- (:) v vs
■ <$>と<*>で書く
string :: String -> Parser String string []    = return [] string (x:xs) = (:) <$> char x <*> string xs ■反復と逐次ができるのは明らか！ ■残るは分岐！
48
プログラム可能コンテナ■コンテナの中身を見て分岐したい！ ■それを実現するのが>>= ■これまでのbindのこと(>>=) :: m a -> (a -> m b) -> m b
■ >>=を持つコンテナのクラス
class Sequential m => Programmable m where (>>=) :: m a -> (a -> m b) -> m b
49

■ファイルがあれば削除import System.Directory removeFileIfExist file = do exist <- doesFileExist file if exist then removeFile file else return () ■あるいはimport Control.Monad import System.Directory removeFileIfExist file = do exist <- doesFileExist file when exist $ removeFile file
50
結局モナドとは何？注： Control.Applicativeをimportすること！ 51
■モナドはチューリング完全■さまざまなDSLを統一されたAPIで実現可能■ Parser ■パーサー ■ IO ■命令型■ Maybe ■失敗するかもしれない計算■ List ■非決定性
52

■ do表記■ DSL (文脈)の交換■ MaybeとListの交換■実装の差し替え■ Parserの実装はモナドのインスタンスであることが多いので、実装の差し替えはあまり苦労しない■例：binaryをattoparsecへ変更■モナド変換子■モナド自体を合成できる■状態のないattoparsecへ状態を足す
53
モナドの神話
■モナドが実行順序を制御する→違います→ m >>= fで、fを評価するには正格なmを必要とするので記述順になるだけです→たとえばx > 0 && x < 100と書けば、この式は記述順に評価されるのと同じことです■ IOモナドは副作用をカプセル化する→意味が分かりません→ "A History of Haskell"でもこの表現が使われていましたorz ■ IOモナドが参照透明性を守る→参照透明になるのは「IOは命令書」というアイディアです→ IOがモナドであることとは、ほとんど関係ありません■圏論が分からないとHaskellのモナドは使えない→僕は圏論を理解していません54 Monadとは単なる型クラスの一つ構文糖衣doの存在がMonadを特殊にしている
55

■階層構造を反映できてないclass Functor f where fmap    :: (a -> b) -> f a -> f b class Functor f => Applicative f where pure   :: a -> f a (<*>)  :: f (a -> b) -> f a -> f b class Monad m where return :: a -> m a (>>=)  :: m a -> (a -> m b) -> m b ■多くのMonadのインスタンスは、 FunctorとApplicativeのインスタンスにもなっている■例外) Parsec 2はMonadのインスタンスだが、 Applicativeのインスタンスではない■なので実用上は、階層構造があると思って問題ない
56

■実際の構文糖衣do
■演算子>> m1 >> m2 = m1 >>= \_ -> m2 57
■ Parser ■ Applicativeスタイル： f <$> m1 <*> m2 <*> m3 ■ Monadより弱いのでより安全■ IO ■ do表記■ Maybe ■ >>= ■値の連鎖なので演算子の方がしっくりくるlookup me db >= flip lookup db ◾ ApplicativeスタイルPerson <$> lookup idnt nameDB <*> lookup idnt ageDB ■ List ■ List内包表記
58

■不要な中間変数をなくすcheckArgs :: [String] -> [String] checkArgs [] = ["/dev/stdin"] checkArgs xs = xs do args <- getArgs let args’= checkArgs args L do args <- checkArgs <$> getArgs ■この様式を覚えることが一番大事■意味の理解は後回しでいい
59

■ <$>があれば不要なもの■ fmap、 liftM ■ <*>があれば不要なもの■ ap ■ <$>と<*>があれば不要なもの■ liftM2、 liftM3、 ... ■ liftA2、 liftA3、 ...
60

■ List内包表記pairs n = [ (x,y) x <- [1..n] , y <- [1..n] , x + y == n ] ■ Listのdo表記pairs n = do x <- [1..n] y <- [1..n] guard (x + y == n) return (x,y) ■内包表記はdoの別表現■現在はListに限る■ Scalaのforはモナド内包表記の一種62
■ 1990: Haskell 1.0 ■ Miranda譲りのList内包表記■ 1996: Haskel 1.3 ■モナドが登場■ 1997: Haskell 1.4 ■ List内包表記がモナド内包表記へと一般化された■ doの採用■ 1999: Haskell 98 ■モナド内包表記がList内包表記へと再び限定された■エラーメッセージ構文糖衣を解いた後のだったので意味不明だった■ 2011 ■ List内包表記を再びモナド内包表記へ戻す活動が活発化■エラーメッセージは構文糖衣を解く前のものを表示■参考文献 : "A History of Haskell" 63おめでとうございます■ Typeclassopediaの日本語訳■あどけない話■ Applicativeのススメ■ QAで学ぶMonad ■リストは非決定性のモナド■ Monadとして抽象化すると何が嬉しいの？ ■ ApplicativeよりもMonadの方が力が強い理由■例題で比較する状態系のモナド◾無名関数と>>=に関する質問■ Haskellには副作用がないのか？ ■ Maybeモナドの秘密■すごいHaskellたのしく学ぼう■ Real World Haskell ■ 18章：モナド変換子