すごいH本読書会記録 14章

社内で行っている『すごいHaskellたのしく学ぼう!』の読書会の為の資料をまとめた。
今回は14章の「もうちょっとだけモナド」を読んだ。
この章では様々な種類のモナドと、モナドに関する様々な関数を紹介している。
登場するソースコードの大半は上記の書籍から引用している。

Writerモナド

Writerモナドは計算された値とは別にログの様に振る舞う値を持つモナド。 これを使えば一連の計算を行っている間に何らかの記録が単一のログ値にまとめることが出来る。
ログを記録するという文脈の付いた計算に慣れるために、以下の関数を導入する。

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

この関数は普通の値を引数に取り、文脈(ここではログとして扱いたい文字列)が付与された値を返すが、最初から文脈が付いている値をこの関数の引数として渡したい場合はどうすれば良いか。
そのような関数の実装を以下に示す。

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

この関数を使うと、文字列が計算ごとに結合され、ログの様に振る舞うことが分かる。

ghci> (3, "Smallish gang.") `applyLog` isBigGang
(False, "Smallish gang.Compared gang size to 9")
ghci> (30, "A freaking platoon.") `applyLog` isBigGang
(True, "A freaking platoon.Compared gang size to 9")

applyLogの抽象化

applyLogは(a, String)型の値をとる関数だが、applyLogの実装をよく見ると、必ずしもStringである必要はなく足し合わせることが出来る値であれば良さそうである。
ということは、前に紹介したMonoidを使えば良い。
Monoidを使って改変したapplyLogの実装を以下に示す。

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

これにより、ログはもはや文字列である必要はなく、任意のMonoid値をログとして扱えるようになった。
例えば商品を順に注文していき、最後に合計金額を出力するような計算が可能になる。

import Data.Monoid

type Food = String
type Price = Sum Int

addDrink :: Food -> (Food, Price)
addDrink "beans" = ("milk", Sum 25)
addDrink "jerky" = ("whiskey", Sum 99)
addDrink _         = ("beer", 30)


ghci> ("beans", Sum 10) `applyLog` addDrink
("milk", Sum {getSum = 35})
ghci> ("jerky", Sum 35) `applyLog` addDrink
("whiskey", Sum {getSum = 124})

Writer型

感覚がつかめたと思うのでWriterの型定義を見てみる。

newtype Writer w a = Writer { runWriter :: (a, w) }

結局Writer型は計算の値aとログの値wのタプルをラップしただけだというのが分かる。
WriterのMonadoインスタンスの定義は以下

instance (Monoid w) => Monad (Writer w) where
    return x = Writer (x, mempty)
    (Writer (x, v)) >>= f = let (Writer (y, v')) = f x
                                       in Writer (y, v `mappend` v')

bindの実装は上で見たapplyLogと殆ど同じで、既存のログ(ここではx)に関数を適用した結果のタプルをパターンマッチで取り出し新たな値yと新たなログが追加されたログ値の二値のタプルを返している。

練習問題1

本の中にあるmultWithLog関数を>>=を使って書き直せ

Writerを扱う上での注意

Writerモナドを扱う上で、ログに使う値の種類に気を付けないと計算量が増えてしまうことがある。
Listをログとして使う場合に関していうと、HaskellのListは片方向連結リストなので末尾への要素の追加にO(n)のコストがある。
つまり、

a ++ (b ++ (c ++ (d ++ (e ++ f))))

の様な操作は、新たなリストに対して最後に結合した後のリストを追加しているが、

((((a ++ b) ++ c) ++ d) ++ e) ++ f

の様な操作は、結合した後のリストの最後の要素に新たに作成したリストを追加しているので、追加の度にリストの最後の要素まで辿らなければならず連結元のリストの要素数の分だけ計算量がかかってしまう。
Writerモナドを扱う際も後者の様な計算に成らないように注意しなければならないが、避けられない場合には差分リストというデータ構造を使うことでコストを削減することが出来る。

差分リストについて

差分リスト自体はあるリストを引数として受け取り、別のリストを先頭に付ける関数である。
[1,2,3]というリストと等価な差分リストは\xs -> [1,2,3] ++ xs、空差分リストは\xs -> [] ++ xsとなる。
このような差分リストを結合する関数は以下の様になる。

f = ("dog" ++)
g = ("meat" ++)
f `append` g = \xs -> f (g xs)

それぞれの操作は連結リストの先頭に要素を追加しているだけなので定数時間のコストで計算が終わる。
では実際にnewtypeを使い差分リストを構築してみる。

newtype DiffList a = DiffList { getDiffList :: [a] -> [a] }

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

fromDiffList :: DiffList a -> [a]
fromDiffList (DiffList f) = f []

-- 連結操作の為にmonoidのインスタンスにする
instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

差分リストと通常のリスト間の変換操作にはO(n)かかることに注意すること。

Readerモナド

モナドとしての関数

以前に関数定義演算子(->)はファンクタでありアプリカティブファンクタであることを見たが、実はモナドでもあり以下の様に定義されている。

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

このままでは>>=がどのように動作するのか分かりにくいので>>=を更に分解してみる。

h >>= f = \w -> f (h w) w
-- = (r -> a) >>= (a -> r -> b) = \w -> (a -> r -> b) ((r -> a) w) w

使用例を見てみる。

import Control.Monad.Instance

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

ここで(* 2) (+ 10)はどちらもaddStuff関数の引数を待ち受けており、aとbにはそれぞれ既に引数が渡されたと仮定した場合の結果の値が入っている。 関数モナド(->)はReaderモナドとも呼ばれる。Readerモナドは引数を待ち受けている関数が複数あり、その引数はみんな同じ場合に使われる。
具体的な用法としては、例えばある設定ファイルから読み込んだ値によって振る舞いを変えたい関数が複数ある場合、それらをReaderモナドとして扱えば良い。

練習問題2

addStuffを>>=を使って書き直せ

リゼちゃんの持っている銃について

これはごちうさ住民 Advent Calendar 2014の21日目の記事です。 この記事ではリゼちゃんの持っている銃の種類について書きます。

リゼちゃんの銃

f:id:komlow:20141220170422p:plain

f:id:komlow:20141220170715p:plain

最初にリゼちゃんのこのシーンを観た時は全く展開が分からず1話で切ろうかと思った。 この銃を特定しようと思い色んなシーンを見てみたもののあまり特徴も無く微妙にデフォルメされていて単純にピストルの画像と見比べてもよく分からなかった。

答え

銃の特定に難儀していたところ、試しに「リゼ 拳銃 種類」でググったら2秒で見つかった。 この銃はわりとポピュラーな銃で色んな漫画やアニメで使われているらしい。

ただ何故この銃だと特定できたのか根拠が不明でありアニメのこのシーン

f:id:komlow:20141220171829p:plain

を見ると撃鉄が無いのでM92ではないのではと思ったが、漫画を見ると撃鉄が確認できるのでアニメではデフォルメの過程で撃鉄が省かれたのかもしれない。(上記のwikiでもジャンルが「漫画」になっているのでもしかしたら漫画を根拠にこの銃だとしたのかもしれない)。

ちなみにごちうさのアニメ制作を担当しているWhite Foxが過去に担当したアニメにヨルムンガンドという銃火器が大量に出てくるアニメがあるが、上記のwikiでは作中に出てくる銃火器の一覧があって楽しい。