Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
すごいHaskell読書会 in 大阪 2週目 #16.5

すごいHaskell読書会 in 大阪 2週目 #16.5

第14章「もうちょっとだけモナド」

参考:以前の読書会の資料

モナドの復習(第13章)

Monad 型クラス

class Monad m where
	return :: a -> m a
	(>>=) :: m a -> (a -> m b) -> m b
	...
  • return は、値をモナド値にします。
  • >>=(バインド)は、モナド値 m a に関数 a -> m b を適用してモナド値 m b を返します。

Maybe モナド、リストモナド

instance Monad Maybe where
	return x = Just x
	Nothing >>= f = Nothing
	Just x >>= f = f x
	...

instance Monad [] where
	return x = [x]
	xs >>= f = concat (map f xs)
	...
  • Maybe モナドは、失敗の可能性があるという文脈付き値を表します。
  • リストモナドは、非決定性計算という文脈付き値を表します。

モナドの関心事

>>= によって、「普通の値を受けとって文脈付き値を返す関数」に「文脈付き値」を渡すことができます。

例 : 関数 (\x -> Just (x * 3))Maybe Int 値を渡す。

Just 5 >>= (\x -> Just (x * 3))
-- Just 15
Nothing >>= (\x -> Just (x * 3))
-- Nothing

例:連続して適用する(13.4 ピエールの綱渡りの例)。

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

do 記法

モナド適用が入れ子になる場合があります。

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)

14.1 Writer? 中の人なんていません!

Writer モナドは、もうひとつの値(ログ)が付加された文脈付き値を表します。

applyLog 関数

isBigGang :: Int -> Bool
isBigGang x = x > 9

この関数を、ログをあわせて返すようにしたかったら、次のようになります。

isBigGang :: Int -> (Bool, String)
isBigGang x = (x > 9, "Compared gang size to 9.")

この関数に、Int ではなく、すでにログがついた値 (Int, String) を渡したい。

そこで、次のような applyLog 関数を用意します(Maybe モナドのときに applyMaybe 関数を考えたのと同様)。

applyLog :: (a, String) -> (a -> (b, String)) -> (b, String)
applyLog (x, log) f = 
	let (y, newLog) = f x
	in  (y, log ++ newLog)

(個人的には、let ... in ... ってなんだったっけ? と思ってしまった。3.4 で出てきた構文)

これにより、もともとあったログに新しいログを追加する、ということが実現できます。

(3, "Smallish gang.") `applyLog` isBigGang
-- (False, "Smallish gang.Compared gang size to 9.")

モノイドが助けにきたよ

ログを String 型からリストにしたい。String もリストも ++ で結合するのは同じなので、applyLog 関数の型は次のように変えられます(関数の実装は先ほどと同じ)。

applyLog :: (a, [c]) -> (a -> (b, [c])) -> (b, [c])
applyLog (x, log) f = 
	let (y, newLog) = f x
	in  (y, log ++ newLog)

では、ログを Bytestring 型にしたいと思ったらどうでしょうか。今度は ++ では結合できません(append 関数を使う必要がある)。applyLogBytestring 版が必要・・・?

実はリストも Bytestring もモノイドでした。このため、applyLog を次のようにすれば、どちらでも OK です。

applyLog :: (Monoid m) => (a, m) -> (a -> (b, m)) -> (b, m)
applyLog (x, log) f = 
	let (y, newLog) = f x
	in  (y, log `mappend` newLog)

この結果、applyLog が付加する値は「ログ」に限定しなくてもよくなりました。モノイド値であれば何でもよいです。例えば、本の addDrink の例では「注文」に「注文の合計金額」を付加しています。

Writer 型

Writer モナドは、モノイド値が付加された文脈付き値を表します。Writer w は、モノイド w が付加されたモナドです。

  • returnmempty を付加した値を返す。
  • >>=mappend でモノイド値を結合する。(applyLog と同様)

前回 #16 でも話があったように、現在の Writer は本の記載とは異なります。本には「開発者は内部実装を変える権利を保持しておきたいそうで」とありますが、実際に内部実装が変わっているようです。

Writer は値コンストラクタがエクスポートされていない代わりに、以下があります(result が文脈なしの値、output が付加されるモノイド値を意味する)。

  • writer : (result, output) タプルを Writer 値にします。
  • runWriter : Writer 値を (result, output) タプルにします。

Writer を do 記法で使う

Writer モナドで、Int にログを付加する例です。

import Control.Monad.Writer

logNumber :: Int -> Writer [String] Int
logNumber x = writer (x, ["Got number: " ++ show x])

これを使って、計算にログを付加する例です。

multWithLog :: Writer [String] Int
multWithLog = do
	a <- logNumber 3
	b <- logNumber 5
	return (a * b)

実行すると Writer 値が返ってくるので、runWriter でタプルに変換して出力します。

runWriter multWithLog
-- (15,["Got number: 3","Got number: 5"])

なお、tell を使うと、モノイド値だけを追記することができます。

multWithLog :: Writer [String] Int
multWithLog = do
	a <- logNumber 3
	b <- logNumber 5
	tell ["Gonna multiply these two"]
	return (a * b)

runWriter multWithLog
-- (15,["Got number: 3","Got number: 5","Gonna multiply these two"])

プログラムにログを追加しよう!

gcd' :: Int -> Int -> Int
gcd' a b
	| b == 0 = a
	| otherwise = gcd' b (a `mod` b)

上記のユークリッドの互除法の関数に、ログ追加版を作ってみます。

import Control.Monad.Writer

gcd' :: Int -> Int -> Writer [String] Int
gcd' a b
	| b == 0 = do
		tell ["Finished with " ++ show a]
		return a
	| otherwise = do
		tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
		gcd' b (a` mod` b)
  • 関数が Writer 値を返すようにする
  • do 記法で tell を挿入する

非効率なリスト構築

ログにリストを使うとき、リスト結合の処理が遅くなる場合があります。

  • a ++ (b ++ (c ++ (d ++ e))) : これは問題ない
  • (((a ++ b) ++ c) ++ d) ++ e : これは遅い

先ほどの gcd' は問題ありませんでしたが、再帰とログが逆になった gcdReverse は遅くなります。

このため、効率のよい結合をサポートするデータ構造を使う方がよいです。そのひとつが差分リストです。

差分リスト

差分リストは、リストを受け取ってリストを返す関数として実装されます。

  • [1,2,3] と等価な差分リストは関数 \xs -> [1,2,3] ++ xs(あるいは ([1,2,3] ++) と書ける)
  • [] と等価な差分リストは関数 \xs -> [] ++ xs(あるいは ([] ++)
newtype DiffList a = DiffList { getDiffList :: [a] -> [a] }

toDiffList :: [a] -> DiffList a
toDiffList xs = DiffList (xs ++)

fromDiffList :: DiffList a -> [a]
fromDiffList f = getDiffList f []

instance Monoid (DiffList a) where
	mempty = DiffList (\xs -> [] ++ xs)
	f `mappend` g = \xs -> getDiffList f (getDiffList g xs)

これを使うと、gcd' は次のようになります。

import Control.Monad.Writer

gcd' :: Int -> Int -> Writer (DiffList String) Int
gcd' a b
	| b == 0 = do
		tell (toDiffList ["Finished with " ++ show a])
		return a
	| otherwise = do
		tell (toDiffList [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)])
		gcd' b (a` mod` b)

14.2 Reader? それはあなたです!

Reader モナドは、共通の値(環境変数)を参照するという文脈付き値を表します。

モナドとしての関数

関数は、ファンクターでありアプリカティブファンクターでもありましたが、さらにモナドでもあります。

instance Monad ((->) r) where
	return x = \_ -> x
	h >>= f = \w -> f (h w) w

Reader モナド

addStuff :: Int -> Int
addStuff = do
	a <- (*2)
	b <- (+10)
	return (a + b)

これを使うと、次のようになります。

addStuff 3
-- 19 ・・・ ((*2) 3) + ((+10) 3)
addStuff 8
-- 34 ・・・ ((*2) 8) + ((+10) 8)

addStuff に引数で渡した値が、各関数(モナド)で共通に参照されます。

本では「関数モナドは Reader モナドとも呼ばれる」という話だけで終わっています。しかし、前回 #16 で話があったように、より一般化された本来の Reader モナドがあります。ただし、この資料では本来の Reader モナドには触れないでおきます。

14.3 計算の状態の正体

State モナドは、状態付き計算という文脈付きの値を表します。

状態付きの計算

状態付きの計算とは、状態を受け取って計算結果と新しい状態を返す関数 s -> (a,s) として表現できます。

例えば、乱数を返す関数は状態付き計算です。乱数ジェネレータを受け取って、乱数値と新しい乱数ジェネレータを返します。

スタックと石

スタック(データ構造)を作ることを考えます。内部のデータはリストで表現し、pop / push 関数を定義します。

type Stack = [Int]

pop :: Stack -> (Int, Stack)
pop (x:xs) = (x, xs)

push :: Int -> Stack -> ((), Stack)
push a xs = ((), a:xs)

しかしこれだと、pop / push にいちいちスタックを渡してやらなくてはならず、不便です。これを解決するのが State モナドです。

State モナド

newtype State s a = State { runState :: s -> (a, s) }

instance Monad (State s) where
  return x = State $ \s -> (x, s)
  (State h) >>= f = State $ \s -> let (a, newState) = h s
                                      (State g) = f a
                                  in g newState
  • h s で状態付き計算 h に現在の状態 s を渡した結果の値 a と状態 newState が出てくる。
  • f a で関数 fa に適用して状態付き計算 g が出てくる。
  • g newState で状態付き計算 g に新しい状態 newState を渡した結果の値と状態が最終結果となる。

これを使って、スタックの定義を書き直します(state 関数は State モナドが定義したもの)。

import Control.Monad.State

type Stack = [Int]

pop :: State Stack Int
pop = state $ \(x:xs) -> (x, xs)

push :: Int -> State Stack ()
push a = state $ \xs -> ((), a:xs)

これで pop / push にスタックを渡す必要はなくなりました。

stackManip = do
	push 3
	pop
	pop

runState stackManip [5,8,2,1]
-- (5, [8,2,1])

状態の取得と設定

MonadState という便利な型クラスがあり、便利な関数 get / put を持っています。

get = state $ \s -> (s, s)
put newState = state $ \s -> ((), newState)

これを使って、pop / push を再度書き直します。

import Control.Monad.State

type Stack = [Int]

pop :: State Stack Int
pop = do
	(x:xs) <- get
	put xs
	return x

push :: Int -> State Stack ()
push x = do
	xs <- get
	put (x:xs)

state 関数を使わずに簡潔に定義できるようになりました。

乱数と State モナド

乱数生成もきれいに書けます。

import System.Random
import Control.Monad.State

randomSt :: (RandomGen g, Random a) => State g a
randomSt = state random

threeCoins :: State StdGen (Bool, Bool, Bool)
threeCoins = do
	a <- randomSt
	b <- randomSt
	c <- randomSt
	return (a, b, c)

乱数ジェネレータを状態として持つことで、明示的に扱う必要がなくなりました。

14.4 Errorを壁に

Either モナドは、失敗の可能性があるという文脈付き値を表します(Maybe と同様)。さらに、失敗に値を持たせられます。

本のインスタンス宣言では Error 型制約がありますが、本の訳注のとおり現在は型制約がありません。

instance Monad (Either e) where
	return x = Right x
	Right x  >>= f = f x
	Left err >>= _ = Left err
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.