- モナド値を操作したりモナド値を返したりする関数
- ここではliftM, join, filterM, foldMを扱う
- ファンクター
- 関数で写せるものを表現
- アプリカティブファンクター
- ファンクターの強化版
- 普通の関数を複数のアプリカティブ値に適用したり普通の値をデフォルト文脈に入れたりできる
- Applicative型クラス定義にはFunctorのインスタンスでなければApplicativeのインスタンスにできない制約がある
- モナド
- アプリカティブファンクターの強化版
- 文脈中の値を何らかの手段で普通の関数に喰わせることが可能
- Applicativeのインスタンスであるべきという制約があるべきだがMonadの方がApplicativeより先に導入された経緯があるため付いていない
- liftM関数
- 関数とモナド値を取って、関数でモナド値を写してくれる
- fmapそのもの
- これがあればモナドがファンクタでなくても大丈夫
- liftMとfmapの型定義
liftM :: (Monad m) => (a -> b) -> m a -> m b
fmap :: (Functor f) => (a -> b) -> f a -> f b- liftMとfmap
- FunctorインスタンスとMonadインスタンスがそれぞれファンクター則とモナド則を満たしていたら両者は全く同じもの
- pureとreturnが常に同じことをするのと似ている
GHCi> import Control.Monad
GHCi> import Control.Monad.Writer
GHCi> liftM (*3) (Just 8)
Just 24
GHCi> fmap (*3) (Just 8)
Just 24
GHCi> -- Writer値コンストラクタはエクスポートされていないので使えない
GHCi> runWriter $ liftM not $ writer (True, "chickpeas")
(False,"chickpeas")
GHCi> runWriter $ fmap not $ writer (True, "chickpeas")
(False,"chickpeas")- 前回作成した以下のStackおよびpop, pushの利用
-- stack.hs --
import Control.Monad.State
type Stack = [Int]
-- 既存のState Stack Int型からStackの先頭の値xを取り出し、
-- それと残りのStackであるxsをタプルにした(x, xs)を
-- state関数に渡すことでState Stack Int型に再び変換して返す
-- xが条件付き計算の計算結果であり、xsが新しい状態となる
pop :: State Stack Int
pop = state $ \(x:xs) -> (x, xs)
-- Intの値aと既存のState Stack Int型であるxsを引数に取り、
-- 計算結果が無いことを表す()と、aとxsを連結したa:xsのタプルを
-- state関数に渡すことでState Stack Int型に再び変換して返す
push :: Int -> State Stack ()
push a = state $ \xs -> ((), a:xs)- popの返り値であるState Stack Intモナドに対し、liftM (+100)を実行することでInt部分(popされた値)に対し+100をしたState Stack Intモナドが返る
- fmapも同様
GHCi> :l stack.hs -- Stackの定義とpop、push関数をload
GHCi> runState (liftM (+100) pop) [1,2,3,4]
(101,[2,3,4])
GHCi> runState (fmap (+100) pop) [1,2,3,4]
(101,[2,3,4])- 以下解説
GHCi> -- popはStackとIntのタプルを内部に持つState型を返す状態付計算
GHCi> :t pop
pop :: State Stack Int
GHCi> -- runStateはState s a型を返す状態付き計算と状態sを引数に取り、計算結果と新状態のタプルを返す
GHCi> :t runState
runState :: State s a -> s -> (a, s)
GHCi> runState pop [1,2,3,4] -- runState 状態付計算 状態
(1,[2,3,4]) -- (計算結果, 新状態)
GHCi> :t runState pop [1,2,3,4]
runState pop [1,2,3,4] :: (Int, Stack)
GHCi> :t liftM
liftM :: Monad m => (a1 -> r) -> m a1 -> m r
GHCi> -- (a1 -> r)が(+100)、m a1がpopの返り値
GHCi> -- Stateモナドに対してliftM (+100)を実行すると状態付き計算の計算結果に対して作用する
GHCi> :t liftM (+100) pop
liftM (+100) pop :: StateT Stack Data.Functor.Identity.Identity Int- Functor型クラスを全く参照せずに実装されている
- fmapはモナドが提供する昨日だけを使って実装可能
- モナドはファンクター以上に強いと言える
liftM :: (Monad m) => (a -> b) -> m a -> m b
liftM f m = m >>= (\x -> return (f x))
-- do記法を使った記法
liftM :: (Monad m) => (a -> b) -> m a -> m b
liftM f m = do�
x <- m
return (f x)- アプリカティブファンクターもモナドの性質を使って実現可能
GHCi> import Control.Applicative
GHCi> -- <$>と<*>を使うとApplicative値に対して(+) 3 5と普通の値のような並びで呼んでいるようにみなせる
GHCi> (+) <$> Just 3 <*> Just 5
Just 8
GHCi> (+) <$> Just 3 <*> Nothing
Nothing<$>はただのfmap<*>はApplicative制約の付いたf aという値を引数に取り、それをApplicative制約の付いた関数に適用することでApplicative値であるf bを返り値として得る- fmapに似ているが関数自体も文脈fの中に入っている
GHCi> :t (<$>)
(<$>) :: Functor f => (a -> b) -> f a -> f b
GHCi> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
GHCi> (+) <$> Just 3 <*> Just 5
Just 8
GHCi> :t (+)
(+) :: Num a => a -> a -> a
GHCi> -- <$>における(a -> b)が(+)に相当((+)の型はa -> a -> a)なのでbがa -> aとなる)
GHCi> :t (+) <$> Just 3
(+) <$> Just 3 :: Num a => Maybe (a -> a)
GHCi> -- よってこれとJustかNothingを更に<*>でつなぐと<*>の定義におけるf bが得られる(<*>)もMonad型クラスが提供する機能だけで実装可能- ap関数
ap :: Monad m => m (a -> b) -> m a -> m b
ap mf m = do
f <- mf -- 結果が関数であるようなモナドから関数を取り出す
x <- m
return (f x)- 使用例
- モナドはアプリカティブ以上に強い
GHCi> Just (+3) <*> Just 4
Just 7
GHCi> Just (+3) `ap` Just 4
Just 7
GHCi> [(+1), (+2), (+3)] <*> [10,11]
[11,12,12,13,13,14]
GHCi> [(+1), (+2), (+3)] `ap` [10,11]
[11,12,12,13,13,14]- 型がモナドである場合
returnをpure,apを<*>とすればApplicativeのインスタンスになるliftMをfmapとすればFunctorのインスタンスになる
- liftA2関数
- 関数を2つのアプリカティブ値に適用する時に便利な関数
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA2 f x y = f <$> x <*> y- liftM2関数
- Applicative型クラス制約がMonadになったもの
- liftM3, liftM4, liftM5などもある
- モナドの威力はアプリカティブやファンクター以上
- すべてのモナドはファンクターでありアプリカティブファンクターでもあるがFunctorやApplicative Functorのインスタンスになっているとは限らない
-
モナドの入れ子を平らにする
Just (Just 4)をJust 4にするような操作- モナドの性質で可能
- join関数を利用
-
join関数の型と実装
join :: Monad m => m (m a) -> m a
join mm = do
m <- mm
mGHCi> join (Just (Just 9))
Just 9
GHCi> join (Just (Just Nothing))
Just Nothing
GHCi> join Nothing
Nothing- ただのconcat
GHCi> join [[1,2,3],[4,5,6]]
[1,2,3,4,5,6]- Writerはexportされてないのでwriterを使う
- joinによりモノイド値がmappendされる
GHCi> import Control.Monad.Writer
GHCi> runWriter $ join (writer (writer (1, "aaa"), "bbb"))
(1,"bbbaaa")GHCi> join (Right (Right 9)) :: Either String Int
Right 9
GHCi> join (Right (Left "error")) :: Either String Int
Left "error"
GHCi> join (Left "error") :: Either String Int
Left "error"- 外側の状態付き計算を走らせてから出てきた計算を走らせるような状態付き計算となる
- ラムダ式は状態を取って2と1をスタックに積み状態付き計算を結果として返す状態付き計算
- joinすると2と1がスタックに積まれpush 10が実行される
GHCi> :l stack.hs
GHCi> runState (join (state $ \s -> (push 10, 1:2:s))) [0,0,0]
((),[10,1,2,0,0,0])join :: Monad m => m (m a) -> m a
join mm = do
m <- mm
m- mmはMaybeの場合はJust (Just 8)
- あるモナド値mとある関数fがあったとき以下は一致
- m >>= f
- join (fmap f m)
- モナド値を関数で写して出てきた入れ子のモナド
- Monadインスタンスを自作するときは入れ子になったモナドを平らにする方法を導く方が>>=の実装を導くよりも簡単
- join関数はファンクターやアプリカティブファンクターだけでは実装できない
- filter関数がHaskellプログラミングの米、mapが塩
- filterの実装
- 述語とリストをとってリストを返す
filter :: (a -> Bool) -> [a] -> [a]-
述語の返り値がモナドの場合
- TrueやFalseに["Accepted the number 5"]などが付いている
- この場合は結果のリストにも同じ文脈が付いていて欲しい
- Control.MonadのfilterMがそのための関数
- TrueやFalseに["Accepted the number 5"]などが付いている
-
filterMの型
- 述語の返り値と同じ文脈が返り値のリストにも付いている
filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]- filterの実行例
GHCi> filter (\x -> x < 4) [9,1,5,2,10,3]
[1,2,3]- Writerを使って何をしたかのログを残す例
- Writer [String] Boolはいわばモナディック述語
-- keepSmall.hs
import Control.Monad.Writer
keepSmall :: Int -> Writer [String] Bool
keepSmall x
| x < 4 = do
tell ["Keeping " ++ show x]
return True
| otherwise = do
tell [show x ++ " is too large, throwing it away"]
return False- 実行例
GHCi> :l keepSmall.hs
GHCi> runWriter $ filterM keepSmall [9,1,5,2,10,3]
([1,2,3],["9 is too large, throwing it away","Keeping 1","5 is too large, throwing it away","Keeping 2","10 is too large, throwing it away","Keeping 3"])
GHCi> fst $ runWriter $ filterM keepSmall [9,1,5,2,10,3]
[1,2,3]
GHCi> mapM_ putStrLn $ snd $ runWriter $ filterM keepSmall [9,1,5,2,10,3]
9 is too large, throwing it away
Keeping 1
5 is too large, throwing it away
Keeping 2
10 is too large, throwing it away
Keeping 3-
filterMを使ってあるリストの冪集合を作る
- 部分集合をすべて含んだ集合
-
リストの各要素に対して、それぞれの要素を残すか除くか両方の答えを返す述語を作る非決定性計算を使う
-- powerset.hs
import Control.Monad
powerset :: [a] -> [[a]]
powerset xs = filterM (\x -> [True, False]) xs- 実行例
GHCi> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]- foldlのモナド版
- モナド値を返す関数とアキュムレータの初期値、畳み込みたいリストを取って1つのモナド値を返す
GHCi> :t foldl
foldl :: (b -> a -> b) -> b -> [a] -> b
GHCi> :t foldM
foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a
GHCi> foldl (\acc x -> acc + x) 0 [2,8,3,1]
14- 整数のリストを加算したいがリストのいずれかの要素が9より大きければ計算全体を直ちに失敗させたい
-- binSmall.hs --
binSmalls :: Int -> Int -> Maybe Int
binSmalls acc x
| x > 9 = Nothing
| otherwise = Just (acc + x)GHCi> :l binSmalls.hs
GHCi> foldM binSmalls 0 [2,8,3,1]
Just 14
GHCi> foldM binSmalls 0 [2,11,3,1]
Nothing- 10章とは異なり間違った文法が入力された場合にエラー処理機能が走るRPN電卓を作る
- RPN電卓の実装
"1 3 + 2 *"のような文字列を引数に取る["1","3","+","2","*"]のような単語に分解- 数をスタックに詰んだりスタックの上から数を取って足し算やら割り算を行う2引数関数を使って空のスタックから初めてリストの内容を畳み込む
import Data.List
solveRPN :: String -> Double
solveRPN = head . foldl foldingFunction [] . words
foldingFunction :: [Double] -> String -> [Double]
foldingFunction (x:y:ys) "*" = (y * x):ys
foldingFunction (x:y:ys) "+" = (y + x):ys
foldingFunction (x:y:ys) "-" = (y - x):ys
foldingFunction xs numberStirng = read numberStirng:xs- foldingFunctionの返り値をMaybeにする
foldingFunction :: [Double] -> String -> Maybe [Double]readMaybe :: (Read a) => String -> Maybe a
readMaybe st = case reads st of
[(x, "")] -> Just x
_ -> NothingGHCi> -- reads関数の挙動 --
GHCi> reads "1 2 3" :: [(Int, String)]
[(1," 2 3")]
GHCi> reads " 1 2 3" :: [(Int, String)]
[(1," 2 3")]
GHCi> reads " s1 2 3" :: [(Int, String)]
[]
GHCi> -- readMaybe関数の挙動 --
GHCi> readMaybe "1" :: Maybe Int
Just 1
GHCi> readMaybe "GOTO HELL" :: Maybe Int
NothingfoldingFunction :: [Double] -> String -> Maybe [Double]
foldingFunction (x:y:ys) "*" = return ((y * x):ys)
foldingFunction (x:y:ys) "+" = return ((y + x):ys)
foldingFunction (x:y:ys) "-" = return ((y - x):ys)
foldingFunction xs numberStirng = liftM (:xs) (readMaybe numberStirng)GHCi> readMaybe "1" :: Maybe Int
Just 1
GHCi> readMaybe "GOTO HELL" :: Maybe Int
Nothing- foldMの結果はMaybe値であり中身にはスタックの最終状態がリストとして入っていおり単一要素となっている筈
- その単一要素である中身にreusltという名前を付ける
- resultはもしfoldMがNothingを返していたらNothingになる
- do記法の中でパターンマッチを使っているので2つ以上の要素が入っていたり空だったりしたらNothingが発生
- 最後にreturnで返すことでMaybe値として提示
- その単一要素である中身にreusltという名前を付ける
solveRPN :: String -> Maybe Double
solveRPN st = do
[result] <- foldM foldingFunction [] (words st)
return resultGHCi> solveRPN "1 2 * 4 +"
Just 6.0
GHCi> solveRPN "1 2 * 4 + 5 *"
Just 30.0
GHCi> solveRPN "1 2 * 4" -- 最終状態のスタックが単一要素でないため失敗
Nothing
GHCi> solveRPN "1 8 wharglbllargh" -- readMaybeがNothingを返しているため失敗
Nothing<=<関数は関数合成によく似ているが普通の関数a -> bではなくa -> m bみたいなモナディック関数に作用する- 普通の関数合成と
<=<の例
GHCi> let f = (+1) . (*100)
GHCi> f 4
401
GHCi> let g = (\x -> return (x+1)) <=< (\x -> return (x*100))
GHCi> Just 4 >>= g
Just 401GHCi> :t id
id :: a -> a
GHCi> let f = foldr (.) id [(+8),(*100),(+1)] -- 一つの巨大な関数となる
GHCi> f 1
208.の代わりに<=<を、idの代わりにreturnを使えば良い- foldrをfoldMに変える必要はない
<=<が関数合成をモナド風に行うことを保証するため
- リストモナドの導入の際に出てきた問題
- 以下のような関数を過去に実装
-- startから3手後にいられる場所を列挙
in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight
-- startからendまで3手で行けるか調べる
canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start- 任意の手数に対応可能したinManyを実装可能
- 第一引数に取った回数分moveKnightを合成したものをreturn startに対し(>>=)する
import Data.List
inMany :: Int -> KnightPos -> [KnightPos]
inMany x start = return start >>= foldr (<=<) return (replicate x moveKnight)
canReachIn :: Int -> KnightPos -> KnightPos -> Bool
canReachIn x start end = end `elem` inMany x start- 型が産まれてモナドであると確認され、適切なMonadインスタンスが与えられるまでの過程を例題を通して学ぶ
- モナドは作りたいと思って作るものではなく、後から型が文脈付きの値を表現していてモナドのように振る舞うと分かった場合にMonadインスタンスを与える
-
[3,5,9]のようなリストはどの値を取るか決めかねている非決定的正数
- それぞれの要素に確率を付与したい場合
- [(3,0.5),(5,0.25),(9,0.25)]
- Data.Ratio内のRational型を使う場合
- [(3,1%2),(5,1%4),(9,1%4)]
- それぞれの要素に確率を付与したい場合
-
newtypeで包む
import Data.Ratio
newtype Prob a = Prob { getProb :: [(a, Rational)] } deriving Show- ファンクタにする
- リストはそもそもファンクタ
- 確率値はそのままにする
instance Functor Prob where
fmap f (Prob xs) = Prob $ map (\(x, p) -> (f x, p)) xs- 試してみる
- 確率の総和は常に1
GHCi> fmap negate (Prob [(3,1%2),(5,1%4),(9,1%4)])
Prob {getProb = [(-3,1 % 2),(-5,1 % 4),(-9,1 % 4)]}- リストがモナドなのでモナドであって欲しい
return- リストの場合は値を取って単一要素リストに入れる関数
Probの場合- 最小限の文脈なので単一要素のリストを作るはず
- 確率の方は常にその値を示すということで1にする
>>=m >>= fは常にjoin (fmap f m)と等価であることを踏まえ どうすれば確率リストの確率リストを平らにできるかを考える
-
'a'か'b'の出る確率25%、'c'か'd'の出る確率75%
- 'a'と'b'の出る確率は同様に確からしい
- 'c'と'd'の出る確率は同様に確からしい
- 本の図参照
-
'a'の起こる確率は1/8, "b"も1/8, "c", "d"は3/8
- 全部足すと1になる
-
この状況を確率リストで表すとProbの入れ子となる
thisSituation :: Prob (Prob Char)
thisSituation = Prob
[(Prob [('a',1%2),('b',1%2)], 1%4),
(Prob [('c',1%2),('d',1%2)], 3%4)
]- 平らにするflatten関数を作り、それを
>>=にする
flatten :: Prob (Prob a) -> Prob a
flatten (Prob xs) = Prob $ concat $ map multAll xs
where multAll (Prob innerxs, p) = map (\(x, r) -> (x, p*r)) innerxs- Monadインスタンス
instance Monad Prob where
return x = Prob [(x,1%1)]
m >>= f = flatten (fmap f m)
fail _ = Prob []-
第一法則
return x >>= fとf xは等価である- ある値を
returnでデフォルト文脈に入れ、ある関数をfmapし、それから結果の確率リストを平らにしたとしても、関数が生み出すすべての確率にreturnが作った1%1が掛かるだけなので文脈には影響がない
-
第二法則
m >>= returnはmと等価であるm >>= returnとmが等しいことは第一法則の考察から明らか
-
第三法則
f <=< (g <=< h)と(f <=< g) <=< hが等価である- リストモナドは第三法則を満たしており、かつ掛け算は結合法則を満たす
- 普通のコイン2枚と10回中9回裏が出るいかさまコイン1枚を投げて、全部裏が出る確率を求める
data Coin = Heads | Tails deriving (Show, Eq)
-- 普通のコイン
coin :: Prob Coin
coin = Prob [(Heads,1%2),(Tails,1%2)]
-- いかさまコイン
loadedCoin :: Prob Coin
loadedCoin = Prob [(Heads,1%10),(Tails,9%10)]
-- コイン投げ
flipThree :: Prob Bool
flipThree = do
a <- coin
b <- coin
c <- loadedCoin
return (all (==Tails) [a,b,c])- 実行
- 3枚とも裏が出る確率は9/40であり1/4より少ない
GHCi> :l prob.hs
[1 of 1] Compiling Main ( prob.hs, interpreted )
prob.hs:12:10: Warning:
‘Prob’ 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: Main.
GHCi> getProb flipThree
[(False,1 % 40),(False,9 % 40),(False,1 % 40),(False,9 % 40),(False,1 % 40),(False,9 % 40),(False,1 % 40),(True,9 % 40)]-
Writerを返す2引数関数を用いたfoldMによる整数の畳込みを行うために、9より大きい数が表れた場合は9より小さい数が表れた場合とは異なるログを残すような関数を実装せよ
-
いかさまコインの問題で、結果がFalseになるパターンは7通りある
- 結果が一致する事象の確率をまとめる処理を書け