Parsec を使って Apache のログファイルをパースしてみる

この記事について

この記事は、 Erik さんのを翻訳したものです。

導入

Haskell について知っていればいるほど良いですが、あなたが熱心な Haskeller であるならこの記事は少々退屈に感じるでしょう。

もし Haskell の基本について学びたいのであれば、Learn You A Haskell （邦訳：すごいHaskellたのしく学ぼう）をおすすめします。この本は何度も読みたくなります！また、どのようにプログラムを組んでいくかを詳しく知りたい人は、 Real World Haskell を読みましょう。実践に生かせる練習問題やアドバイスが沢山載っています。私はこのコードを書くとき、この本を頼りに作業をしていました。

Apache はおそらく世界で最も普及しているウェブサーバでしょう。多くのウェブサーバと同じように、様々な情報とともに各リクエストのログをとっています。大きなIT企業はこうした情報を活用しているでしょうが、私達のほとんどはこのログを増やすだけで放置しています。このログを使って何か素晴らしい情報を引き出してみましょう！この記事で取り扱うログフォーマットは Apache combined log format です。これはサンプルです。

192.168.1.80 - - [18/Feb/2011:20:21:30 +0100] "GET / HTTP/1.0" 503 2682 "-" "-"

もしあなたのログファイルが違うフォーマットであるなら、多少の調節が必要です。フィールドは順に：クライアントの IP アドレス、クライアントのアイデンティティ、ユーザ ID、リクエストを受け取った日時、リクエスト、ステータスコード、バイト、 "referer" HTTP リクエストヘッダ、 "user-agent" HTTP リクエストヘッダです。これらの情報が確実に保持できるように、ログのそれぞれの値をパースして、データ型にまとめましょう。さて、定義してみましょう！

data LogLine = LogLine {
	  getIP :: String
	, getIdent :: String
	, getUser :: String
	, getDate :: String
	, getReq :: String
	, getStatus :: String
	, getBytes :: String
	,getRef :: String
	, getUA :: String
} deriving (Ord, Show, Eq)

レコードシンタックスを使ってアクセサを用意しました。また、便利のためにこれらをOrd, Show, Eq 型クラスのインスタンスにしました。

次は、行のパースを実際にパースしましょう。以前、このスクリプトを Python で書いた時、正規表現を用いてパースをしました。すると、コーディングに時間がかかり、また使っている間はずっとバグに出会う羽目になりました。しかし、 Haskell はもっとよい方法を提示してくれています。正規表現を用いるより、 Parsec ライブラリのパーサコンビネータを使いましょう。 小さなパーサをつなげて大きなパーサにするという Parsec のアイデアは、対象物が何であるかを一歩一歩確実に定義していくことを可能にしています。例を見ながらが理解しやすいと思います。

Parsec

上にあるログの例の一行をみると、それぞれの値がスペースで区切られています。しかし、いくつかの値はクォートや角括弧で囲まれた値の中にスペースを含んでいます。ですので、私たちは３つの種類の値をパースすることになります。まずは一番簡単な、スペースを含んでいない値のパーサを定義してみましょう。

plainValue :: Parser String
plainValue = many1 (noneOf " \n")

型シグナチャは、「 plainValue の結果は、 Parser モナドに包まれた String 」と読めます。 Parsec がモナドであることの利点のひとつとして、他のパーサの中でも do 記法で使えるようになることです。 plainValue パーサに話を戻しますが、 最初に many1 を使っています。これは、パーサをひとつとって、それを１つ以上適用し、最終的に値のリストを返すアクションです。私たちのケースでは、スペースでない限り文字を消費したいのです。なぜなら、 Apache のログ行の値はスペースで区切られているからです。このため、文字リストを受け取って、文字が渡されたリストでない場合、その文字をひとつ消費する noneOf を用いています。

これらをつなげて、 many1 (noneOf " \n") はスペースまたは改行に当たるまで文字を消費します。素晴らしい！

次は、角括弧で囲まれた値とクォートで囲まれた値をどうするかを考えましょう。どちらもその地の中にスペースを含む可能性があるため、これらのために特別にパーサを作る必要があります。

brancketedValue :: Parser String
brancketedValue = do
	char '['
	content <- many (noneOf "]")
	char ']'
	return content

quotedValue :: Parser String
quotedValue = do
	char '"'
	content <- many (noneOf "\"")
	char '"'
	return content

これらは do 記法で書かれたパーサです。簡潔なだけでなく、ログ行のフォーマットを表しています！ brancketedValue をみてみましょう：まず、左端にある括弧を消費しています。そのあと、 many1 (noneOf "]") の結果を content という名に束縛します。先ほどの many1 (noneOf " \n") のように、与えられた文字列に該当しない限り、文字を消費していきます。最終的に、最後の文字である右角括弧を消費し、 return によって結果を Parser モナドで包みます。

これですべての値をパースできるようになったので、これらのパーサをどのように使って1行をパースするかを定義しましょう。それぞれの結果を LogLine データ型にまとめたいので、それぞれのパーサの結果を対応する値に結びつける必要があります。さあ、やってみましょう！

logLine :: Parser LogLine
logLine = do
	ip <- plainValue
	space -- スペースをパースしてその結果を捨てる
	ident <- plainValue
	space
	user <- plainValue
	space
	date <- brancketedValue
	space
	req <- quotedValue
	space
	status <- plainValue
	space
	bytes <- plainValue
	space
	ref <- quotedValue
	space
	ua <- quotedValue
	return $ LogLine ip ident user date req status bytes ref ua

多少余分な記述がありそうですが、このパーサを解釈するのは容易です。信じられないもしれませんが、これで終わりです。このスクリプトは Apache combined log スタイルの行をパースします。では実際に例をパースしてみましょう！

testLine = "192.168.1.80 - - [18/Feb/2011:20:21:30 +0100] \"GET / HTTP/1.0\" 503 2682 \"-\" \"-\""

main = case parse logLine "(test)" testLine of
	Left err -> print err
	Right res -> print res

parse は入力に対するパーサの結果を Parsec モナドから引き出し、エラーまたは結果を返します。結果は以下のようになります。

LogLine { getIP = "192.168.1.80"
	, getIdent = "-"
	, getUser = "-"
	, getDate = "18/Feb/2011:20:21:30 +0100"
	, getReq = "GET / HTTP/1.0"
	, getStatus = "503"
	, getBytes = "2682"
	, getRef = "-"
	, getUA = "-"
	}

サンプルコードはここにあります。

さらなるパーサへの誘い

引き続き、Magnus氏のブログの翻訳です。

前回の記事に対して、Conal Elliottから興味深いコメントを頂きました。

もっと関数的でApplicativeな書き方をしてもいいかもね。
doで繋がったParsecコードをliftM, liftM2, ...といったように置換してみよう。読んだ感じできそうだし。parseRegionのところは、残りのスペースを捨てる"thenSpace (many1 digit)"みたいな補助的な関数を用意するといいよ。
あと、parseAddressやparsePerms、parseDeviceのなかにある似たようなパターンをくくり出してみるのもいいね。
くくりだしをすればするほど、よりエレガントなコードになるし、理解もしやすくなるよ。

最初は何を言っているのかわからなかったのですが、（今でも怪しいところだけれど）だいたい意味が分かって来ました。

基本的に、私のコードはdoをすべてのパースするコードに利用しているため、非常に連続的です。個人的にはこれが流れによく似ていて見やすく感じていました。ただ、私自身もこのコードが”関数的”とは言い難いことはわかっていたので、Conalのコメントに従ってみて、どうなるかを見てみたいと思います。

まずは、行の中にあるすべての要素は空白文字で切り離されているものだとします。ただし、いくつかのものは他の文字によって切り離されているとします。なので、最初に私がしたことは、「文字を読み込んで、その次に文字列を読み込んで、（文字によって区切られた、）最初に読み込んだものを返す高階関数」を作ることでした。

thenChar c f = f >>= (\r -> char c >> return r)

スペースがセパレータの役目を果たすため、そういった関数を定義しましょう。

thenSpace = thenChar ' '

parseAddressのなかでこれを使ってみます。

parseAddress = let
	hexStr2Int = Prelude.read . ("0x" ++)
	in do
		start <- thenChar '-' $ many1 hexDigit
		end <- many1 hexDigit
		return $ Address (hexStr2Int start) (hexStr2Int end)

他のパーサ関数も同じようにthenCharやthenSpaceを使って素直に書き直せます。

私が、Conalがコメントで言及していたliftMの部分を完全に理解できたかはちょっと怪しいです。
おそらく私が文字列を読み込んで、それを構造体（データ型）に変換していることについて言及しているのではないかと。liftMを使うことで、その変換作業をコードの中で行うことができます。下のコードは、parseAddressをhexStr2Intを移動させたものです。

parseAddress = let
	hexStr2Int = Prelude.read . ("0x" ++)
	in do
		start <- liftM hexStr2Int $ thenChar '-' $ many1 hexDigit
		end <- liftM hexStr2Int $ many1 hexDigit
		return $ Address start end

こんな感じで他のパース関数も変えて行きました。

parsePerms = let
	cA a = case a of
		'p' -> Private
		's' -> Shared
	in do
		r <- liftM (== 'r') anyChar
		w <- liftM (== 'w') anyChar
		x <- liftM (== 'x') anyChar
		a <- liftM cA anyChar
		return $ Perms r w x a
parseDevice = let
	hexStr2Int = Prelude.read . ("0x" ++)
	in do
		addr <- thenSpace parseAddress
		perm <- thenSpace parsePerms
		offset <- liftM hexStr2Int $ thenSpace $ many1 hexDigit
		dev <- thenSpace parseDevice
		inode <- liftM Prelude.read $ thenSpace $ many1 digit
		path <- parsePath <|> string ""
		return $ MemRegion addr perm offset dev inode path

このコードが果たして関数型っぽいかどうかは自信がもてません…。読みやすい…？

以下はコメントです。

Holger

あなたの記事とConalのコメントに触発されてliftMと遊んでみて、別のヴァージョンのparseAddressを作ってみました。
確かにすべての関数をそのようにかけますね。
けど正直なところ、do記法で書かれたコードのほうがよっぽど読みやすく感じます。

Twan van Laarhoven

パーサを読みやすくする一番の方法はData.Applicativeを使うことです。また、多くの人はlet ... inを好んで使いますね。例えばこんな感じに：

parseHexStr = Prelude.read . ("0x" ++) many1 hexDigit
parsePath = many1 (char ' ') *> many1 anyChar

parseRegion = MemRegion
	parseAddress *> char ' '
	parsePerms *> char ' '
	parseHexStr *> char ' '
	parseDevice *> char ' '
	(Prelude.read many1 digit) *> char ' '
	(parsePath return "")

あと、基本的に、(liftM# f x y z)は f <$> x <*> y <*> zのようにかけます。

Conal Elliott

そうですね、大体あってます。一度doスタイルからliftM#スタイルに変わったら、モナド演算子をApplicativeファンクタ演算子に置き換えていくのは簡単です。

Magnus

Conalへ。
これは、applicativeな演算子を試してみる必要がありそうですね。

パーサへの誘い

Magnusさんのご厚意により、邦訳してもよいことになりましたので掲載させて頂きます。
もとの記事はこちらのAdventures in parsingです。

私はParsecが使いこなせるようになりたいと常日頃から思っていました。何度か試してみたのですが、そのいずれもどこかで躓いて失敗し、そういった期間が非常に長かったので、何度試したかは忘れてしまいました。私の~/devo/test/haskellのなかに書きちらされたコードたちが私の失敗の数々を物語っています。

さて、私の一番最初の試みとして、/proc/< pid >/mapsの中身をパースすることを考えました。
mapsのマニュアルを見てみましょう。

どうやら、

address perms offset dev inode pathname
08048000-08056000 r-xp 00000000 03:0c 64593 /usr/sbin/gpm

という構造になっているようです。

まず、いくつかのデータ型を用意し、つなげていきます。最初にアドレスの範囲を表します。

data Address = Address { start :: Integer, end :: Integer }
	deriving (Show)

パーミッションにsまたはpが入っているものはAccessと呼ぶことにします。

data Access = Shared | Private
	deriving (Show)

rwxのようなパーミッションは簡単にブール型として表しましょう。

data Perms = Perms {
	read :: Bool,
	write :: Bool,
	executable :: Bool,
	access :: Access
}
deriving (Show)

デバイスは素直に。

data Device = Device { major :: Integer, minor :: Integer }
	deriving (Show)

最後に、これらをメモリ空間を表すひとつのデータ型に固めます。

data MemRegion = MemRegion {
	address :: Address,
	perms :: Perms,
	offset :: Integer,
	device :: Device,
	inode :: Integer,
	pathname :: String
}
deriving (Show)

すべてのデータ型はShowのインスタンスとしている（つまり最低でもshowは使える）ので、それらの出力は簡単になっています。

さて、Parsecを使っていきます。トップダウンかボトムアップの方法で開発ができますが、私は後者を選ぶことにしました。しかし、mapsファイルの中の一行がシンプルな形式なので、最終的にどういった関数になるのかが容易に想像できますね。私がボトムアップですると決めたのは、データ型のおかげで、どのように一行を切り離すかが簡単にわかるからです。まず、アドレスの範囲をパースしてみます。

parseAddress = let hexStr2Int = Prelude.read . ("0x" ++)
	in do
		start <- many1 hexDigit
		char '-'
		end <- many1 hexDigit
		return $ Address (hexStr2Int start) (hexStr2Int end)

アドレス自体が１６進数表記で表されており、少なくとも１文字以上の長さがあるので、many1 hexDigitを使っています。count 8 hexDigitのように、アドレスの長さが８文字であるかをチェックするのが安全であるとは思いますが（少なくとも32bitマシンでは）、私は試していません。
１６進数からIntegerに変える方法は２つあります。一つは上でしたようにPrelude.readが0xから始まる文字列を１６進数として読みこんでくれることを利用する方法です。もう一つは fst . (!! 0) . readHexを使ってする方法です。
マニュアルページによると、アドレスはダッシュ'-'で区切られているようなので、char '-'で処理しています。

この関数をテストするのは簡単です。ghciを使ってロードし、parseを使用します。

*Main> parse parseAddress "" "0-1"
Right (Address { start = 0, end = 1 } )
*Main> parse parseAddress "hhh" "01234567-89abcdef"
Right (Address { start = 19088743, end = 2309737967 } )

うまくいっていますね。

次に、パーミッションをパースします。これは素直にかけるのでコメントは必要ないかもしれません。

parsePerms = let
	cA a = case a of
		'p' -> Private
		's' -> Shared
	in do
		r <- anyChar
		w <- anyChar
		x <- anyChar
		a <- anyChar
		return $ Perms (r == 'r') (w == 'w') (x == 'x') (cA a)

デバイス情報も上記のアドレスのものと同じ書き方で実装できますが、今回はダッシュではなくコロン':'で分けられています。

parseDevice = let
	hexStr2Int = Prelude.read . ("0x" ++)
	in do
		maj <- many1 digit
		char ':'
		min <- many1 digit
		return $ Device (hexStr2Int maj) (hexStr2Int min)

次に、MemRegionインスタンスを作り出すためにこれらをつなげましょう。

parseRegion = let
	hexStr2Int = Prelude.read . ("0x" ++)
	parsePath = (many1 $ char ' ') >> (many1 $ anyChar)
	in do
		addr <- parseAddress
		char ' '
		perm <- parsePerms
		char ' '
		offset <- many1 hexDigit
		char ' '
		dev <- parseDevice
		char ' '
		inode <- many1 digit
		char ' '
		path <- parsePath <|> string ""
		return $ MemRegion addr perm (hexStr2Int offset) dev (Prelude.read inode) path

問題は、パス名のない行なんかもあることです。こんな感じで。

address perms offset dev inode pathname
09058000-0805b000 rwxp 00000000 00:00 0

inodeのあとにスペースがあるようなので、parseRegionの中のchar ' 'は残しています。もしパスをパースしようとして失敗したら、空の文字列をパースすることで解決しました。それがparsePath <|> string ""の意味です。パスネームはどうやらスペースの数によって整えられているようですが、面倒なのでスペースをすべて消費しています。パスネームとしてどの文字が使用できるのか把握していないので、文字があったらとにかく消費していくことにしています。

ここで、つくったこの関数で遊ぶために、pidによる指定で特定のプロセスのmapsファイルをパースし、その結果をMemRegionインスタンスのリストで返す関数を考えました。

getMemRegions pid = let
	fp = "/proc" </> show pid </> "maps"
	doParseLine' = parse parseRegion "parseRegion"
	doParseLine l = case (doParseLine' l) of
		Left _ -> "Failed to parse line"
		Right x -> x
	in do
		mapContent <- liftM lines $ readFile fp
		return $ map doParseLine mapContent

上のコードでは、行をIOモナドからうけとり、Parserモナドにそれを渡し、再びIOモナドに返しています。試してみましょう。

*Main> getMemRegions 1

これで実行できますが、ものすごい数で出力されたりするのでtakeを使って制限したりするとよいでしょう。ですので、最後の行は、

return $ map doParseLine (take 4 mapContent)

となります。
さて、これで最初のコマンドライン引数をpidとして受け取るプログラムを書いてみましょう。

main = do
	pid <- liftM (Prelude.read . (!! 0)) getArgs
	regs <- getMemRegions pid
	mapM_ (putStrLn . show) regs

これでパーサは完成です。

ちなみに、以下のモジュールをインクルードする必要があります。

import Control.Monad
import System
import System.FilePath
import Text.ParserCombinators.Parsec

Scalaは関数型プログラミング言語ではない

面白い記事があったので翻訳してみました。
ライセンスはCreative Commonsです。

しばらくScalaで仕事をして、疑う余地なく以下のことが断言できるようになりました。

”Scalaは関数型言語ではありません。クロージャを持ち、静的な型を持つオブジェクト指向言語です。”

なので、みんなが嘘の売り文句を延々と言うのをやめてくれないかなと思っています。
これがどういうことなのかを理解するためには、ScalaのメーリングリストにJon Harropが流した挑発的な文を見てみてください。そのスレッドで、Martin O.が
”オブジェクト指向こそが唯一の”美しい”解である”
と主張しています。のちにMLで、もう少し丁寧にこのことについて述べていて、それによると、アプリケーションの基幹のデータ構造を何度も変更しなくてはならないようなとき、オブジェクト指向が最適な解であると述べてみます。最終的にその議論は泥沼化してしまったのですが、終盤は非常に興味深いものでした。

私が特に気になったのは、Martin O.からのこのポストです。
”abstractである定義、値、型の実装はそのスーパークラスの他のメンバも参照できる。しかし、高階関数やファンクタに対する引数として適用の結果を参照することはできない。だから、抽象の入ったopen recursionはオブジェクト指向プログラミングではサポートされているが、それを関数型で実現するには面倒なことになる（例えばTaPLでのクラスのエンコーディング）。”

さて、この文は少々おかしいです。Pierce本で定義されているように、open recursionは暗黙的にオブジェクト指向の考えであるため、これを関数型プログラミング言語で実現させるなら、違うパラダイムなので無理が生じるのは当たり前ですね。はたして、その技術は関数型プログラミング言語で必要なのか？使うに値するのか？という疑問が湧いてきます。関数型言語は同じ問題に対してもっと良い解をもっているのか、それともそういった馬鹿馬鹿しいことができないように制限されているのでしょうか。

Scalaは関数型プログラミング言語であるかを考えてみます。そもそもScalaはどのように問題を解決しているのでしょうか。Brian Hurtなら、言語の本質についてこう述べるでしょう。
"言語が何かを可能にするのではなくて、言語がなにを簡単にするかが問題なんだ。Scalaは何を簡単にしてくれるんだ？”

この発言に対して、Martin O.は否定的です。
”私達は、関数型とオブジェクト指向のどちらもを美しく高めることを第一としていた。関数はファーストクラスである必要があったし、関数リテラル、そしてクロージャも必要だった。また、他にも型や多相性、パターンマッチングといった機能も欲しかった。そして、Pizza言語で実現できたものよりも、関数型、オブジェクト指向型のどちらの面でも綺麗にしたかった。それこそが、したいことだったんだ。その後、それを実現するのがすごく簡単だってことに気づいた。関数型言語はきちんと体系化された機能をすでに持っていたからね。”
この考えによると、Scalaは関数型言語といえるでしょう。

まずは基本から見て行きましょう。
関数型言語では、当たり前ですが関数をプログラムしていきます。つまり、問題を関数に置き換えることが解となるといえます。OCamlでは、以下のように関数を定義します。

let f x = x + 1;;

しかしScalaでは、少し違った形で定義します。

object SomeHolderObject {
    def f(x:Int):Int = { x + 1 }
}

OCamlでは、関数は直接的に定義されています。Scalaでは関数に対してオブジェクティブな定義を与える必要があります。objectキーワードを使うことで、singletonであるオブジェクトであることを保証していますが、これはJavaでstaticキーワードを使った場合と大して変わりません。ですので、根本的なな構造からすでに関数型言語とは呼べず、むしろオブジェクト指向よりだということが言えます。

さて、Scalaによる抽象化を見てみましょう。Scalaでは、抽象化をするとき、インターフェースやtraitなどの形でするのが普通です。traitはScalaにおけるopen recursionですが、その名に反してオブジェクト指向よりの考えに基づいています。さて、Scalaの基本的な部分がオブジェクト志向よりであること、そしてScalaの抽象化がオブジェクト指向的であるということがわかりました。

ダメ押しとして、Scalaでの関数型プログラミングを見てみましょう。私の大好きなカリー化から行ってみます。

OCamlでは余裕ですね。

let x a b = a + b;;
let y = x 1;;
y 2;; (=> 3)

悪くないですね。
さて、Scalaでやってみます。

def x(a:Int, b:Int) = a + b
def y = x(1)

ところが上のコードではエラーを返してきます。
x: (Int, Int) Intなので引数が足りません…
もう一度やってみます。

def x(a:Int, b:Int) = a + b
def y = Function.curried(x _) (1)
y(2) // 3

…。
カリー化は可能です。一応。ただし、本当の関数型言語に比べてひどく面倒です。まあ、このへんはまだ良いとしましょう。ちょっとぐらい汚くてもいいです。さて、次はもっと代数的な関数型プログラミングとして基本的なことをしてみましょう。

関数型言語でよく使われる、OCamlのvariant型のような代数的データ型はどうでしょう。OCamlやF#、Haskellではパターンマッチングという強力な機能を提供してくれています。Scalaはどうでしょうか。

OCamlではこうかけますね。

type robert = Foo of int | Bar of string | Baz;;

Scalaだとこうなります。

sealed abstract class Robert;
sealed case class Foo(value:Int) extends Robert;
sealed case class Bar(value:String) extends Robert;
sealed case class Baz extends Robert;

…。私も最初は、こいつがcase classの継承のためにきちんと書かれたコードなんだろうなって思ってました。だからオプション的なあれかと。でもどうやら必ず書かなくてはならないようで、そうなるとOCaml版のものと比べてひどくうっとおしいコードなだけですね。

さて、ここでもう一度考えます。Scalaは関数型プログラミングを簡単にしてくれているだろうか？
いいえ、全く。全然。

じゃあなぜScalaが関数型言語だと言われたのでしょうか？関数がファーストクラスだから？PerlやRuby、Groovyもそれは備えてるのに関数型言語とは呼ばれませんね。静的型付けのクロージャ？ならC#はどうなるのでしょうか。パターンマッチング？オブジェクト指向のスタイルで簡単に実現できますね。無駄のない実装で。イミュータブルな傾向があるから？それはいいことですが、ただそれだけなら関数型言語と呼ばれるには程遠いですね。

Scalaは関数型言語ではありません。なぜなら、関数型のプログラミングスタイルを全然簡単にしてくれないからです。可能ではありますし、関数型らしいところもありますが、根本的にScalaは関数型ではありません。OCamlはオブジェクト指向のプログラミングを可能にしますので、オブジェクトな部分を持ちます。しかしOCamlは根本的にはオブジェクト指向ではありません。それは全然問題無いです。…でもここは引き分けにしておきましょうか。

ただ、勘違いしてほしくないので。
ScalaはJVM上で動く言語として、大きな飛躍です。今C#はJavaを正真正銘、はるかに上回っていますし、ScalaはC＃を超えてJVMを舞台の先頭に引き戻すための素晴らしい試みであると言えます。しかし、Scalaが王道的な”オブジェクト指向型言語”であることを踏まえると、”関数型プログラミング言語”と呼ぶのはやめたほうが良いのではないでしょうか。欺瞞に聞こえますし、なにより「関数型プログラミング言語とはなにか」を押し下げているように見えます。

Haskellモナドトランスフォーマー(12)

今まで、MaybeTとListTという２つの非常に単純なモナドトランスフォーマーの実装をしてきました。それから、少し遠回りをしてモナドをそれのトランスフォーマーに持ちあげるという話もしましたね。ここでは、その二つの考えを、StateTという標準ライブラリの中でも興味深いトランスフォーマーの実装を見ながらつなげてみましょう。このトランスフォーマーを学ぶことで、モナドトランスフォーマーをコードの中で使用するときに、トランスフォーマーのメカニズムがはっきりと見えてくるようになります。もしもわかりにくかったら、過去のStateモナドについての記事を読んでみてください。

Stateモナドが

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

と定義されているように、StateTトランスフォーマーも

newtype StateT m a = StateT { runStateT :: (s -> m (a, s)) }

と定義されています。
State sはMonadクラスとMonadState sクラスのどちらのインスタンスでもあります。なので、StateT s mもMonadとMonadState sクラスのメンバーですし、更にいうと、もし、mがMonadPlusのインスタンスならStateT s mもまたMonadPlusのメンバーであるべきです。

StateT s mをMonadのインスタンスとする実装は以下のようになります。

State

newtype State s a = State { runState :: (s -> (a, s)) }
instance Monad (State s) where
	return a = State $ \s -> (a, s)
	(State x) >>= f = State $ \s ->
		let (v, s') = x s
		in runState (f v) s'

StateT

newtype StateT s m a = StateT { runStateT :: (s -> m (a, s)) }
instance (Monad m) => Monad (StateT s m) where
	return a = StateT $ \s -> return (a, s)
	(StateT x) >>= f = StateT $ \s -> do
		(v, s') <- x s
		runStateT (f v) s'

このreturnの定義は、内側のモナドのreturnを使用し、それを結果とし、>>=演算子は内側のモナドの計算をするためにdoブロックを使用しています。

また、StateTトランスフォーマーを使用し、MonadStateクラスのインスタンスとするすべての合成モナドも定義したいのでgetとputを定義しましょう。

instance (Monad m) => MonadState s (StateT s m) where
	get = StateT $ \s -> return (s, s)
	put s = StateT $ \_ -> return (( ), s)

MonadPluのインスタンスとするために、StateTがMonadPlusとともに使用される合成モナドの定義もしましょう。

instance (MonadPlus m) => MonadPlus (StateT s m) where
	mzero = StateT $ \s -> mzero
	(StateT x1) `mplus` (StateT x2) = StateT $ \s -> (x1 s) `mplus` (x2 s)

最後に、StateTモナドをMonadTransクラスのインスタンスとしてliftもつけ、Haskellのモナドクラスとして完成させましょう。

instance MonadTrans (StateT s) where
	lift c = StateT $ \s -> c >>= (\x -> return (x, s))

関数liftは、内側のモナドの計算を、入力された状態に結びつける関数に結びつける、状態変換関数StateTを作り出します。結果として、例えばStateTをListモナドに適応した時、結果としてリストを返す関数（Listモナド内の計算）は、StateT s [ ]に持ち上げられ、StateT (s -> [ (a, s) ]を返す関数になります。持ち上げられた計算は複数の (値, 状態) というペアを入力より生成し返します。
この結果として、StateTの計算をコピーして、持ち上げられた計算によって返されたリスト内のそれぞれの計算結果に対して違う計算を生成すます。もちろん、StateTを違うモナドに対して適応するのは違うセマンティクスのliftを生成します。

Haskellモナドトランスフォーマー(11)

liftの実装はわりと素直です。MaybeTトランスフォーマーの場合を見てみます。

instance MonadTrans MaybeT where
	lift mon = MaybeT (mon >>= return . Just)

内側のモナドを値に適用し、サンドイッチで言う真ん中までの処理を行ったあと、>>=演算子と型コンストラクタを使用して最下層のモナドを真ん中のスライスの下に潜り込ませます。その後、MaybeTコンストラクタを使用してサンドイッチを完成させます。関数liftを使用することで、３つの層をもつモナドサンドイッチに変換することができます。

liftMがどの型に対しても適用できる関数であるのに対して、liftが個別の定義が必要である理由を考えてみてください。

Haskellモナドトランスフォーマー(10)

モナドトランスフォーマーによって合成されたモナドを使うとき、内側のモナドをきちんと考える必要がないようにしたいところです。そのほうが綺麗でシンプルなコードになるからです。内側のモナドの型を持った値を扱う計算の中でdoブロックを使うより、内側のモナドを合成モナドまで持ち上げる命令を使ったほうが良いでしょう。

liftMは、モナディックでない関数をモナドに持ち上げる関数だったことを思い出してください。各モナドトランスフォーマーはモナディックな計算を合成モナドに持ち上げる関数liftを用意しています。

MonadTransクラスはControl.Monad.Transの中で定義されており、liftという関数１つだけを提供します。

class MonadTrans t where
	lift :: (Monad m) => m a -> t m a

IO処理を持ち上げるために最適化されたモナドはMonadIOクラスのメンバーとして定義されており、関数liftIOと名付けられています。

class (Monad m) => MonadIO m where
	liftIO :: IO a -> m a