読者です 読者をやめる 読者になる 読者になる

りんごがでている

何か役に立つことを書きます

モナドトランスフォーマー・ステップ・バイ・ステップ(Monad Transformers Step By Step)

Haskell 翻訳

著者のMartin Grabmüller氏に許可をいただきましたので、 Haskellモナドトランスフォーマーチュートリアルを翻訳したものを公開します。

タイポや誤訳、プログラムのミス等ありましたら、 Twitter宛@かコメント欄までご連絡頂けるとありがたいです。

元のテキストやプログラムは以下のリンクから得られます。

Monad Transformers Step by Step

  • [2012/12/19] 誤りを多数訂正しました。id:qtamakiさん、ありがとうございます。
  • [2014/6/19] 誤りを2点訂正しました。id:daimatzさん、id:hitotakuchanさん、ありがとうございます。

Monad Transformers Step by Step

Martin Grabmüller Oct 16 2006

概要(Abstract)

このチュートリアルでは、Haskellのプログラムに徐々に機能を追加していくためには、どのようにモナドトランスフォーマー(Monad Transformer)を利用したらよいかを説明します。

これはモナドトランスフォーマー自体の「実装」に関するものではありません。 エレガントでスッキリしていて、なおかつ強力なHaskellプログラムを書くために、いかにモナドトランスフォーマーを「利用」するかについてのチュートリアルです。

単純な式を評価する関数から始め、モナドスタイルに変えてから、モナドトランスフォーマーを構築しつつ、エラー処理、環境渡し、状態、ログ、入出力といった機能を加えていきます。

1 イントロダクション(Introduction)

このチュートリアルでは、Haskellモナドトランスフォーマーへステップ・バイ・ステップで紹介していきます。

モナドは、プログラムを組み上げていく上で、柔軟で拡張性を持つ非常にエレガントな手法です。 モナドHaskellのような遅延評価関数型言語ではとても興味深いもので、純粋関数型のプログラムに副作用を統合させることができます。 さらに、モナドを使ってプログラムを構築していくことで、ちょっとした定義があれば、色々なアルゴリズムの必要な記録処理や裏側の処理の多くを隠すことができ、注目してるアルゴリズムに集中することができます。

モナドトランスフォーマーモナドを使ったプログラミングをさらに便利にしてくれます。 違ったモナドや型やモナドを連結する関数のライブラリを提供してくれるので、必要なモナドトランスフォーマーを組み合わせて特製のモナドを作ることができます。 例えば、状態とエラー処理を備えたモナドが欲しいなら、StateTとErrorTふたつのモナドトランスフォーマーを選んできて組み合わせればよいのです。 このチュートリアルの目的は、シンプルな関数から始め、それをステップ・バイ・ステップで機能を拡張すべく色々とモナドを操って広げていく様を優しく紹介することです。 このチュートリアルモナドトランスフォーマーの概念の裏に潜んだ理論についてのものではありませんし、実装についてのものでもありません(うまいことモナドトランスフォーマーを使うのに必要なものは除く)。

ここでは、Haskellモナドクラスとかdo記法などといった、モナドを使ったプログラミングの機能や基礎については知っていることを想定しています。他のことは途中で追々説明していきます。

ここにあるHaskellのプログラムは現在のHaskell98標準のものではない機能を使っています。Control.Monad.Errorなどは標準ライブラリのモジュールではありません。 こうしたモジュールにある階層的なモジュール名も細かい実装もHaskell98の範疇ではありません。 しかしながら、こうした拡張は現在のGHC[1]ではちゃんとサポートされています。 プログラムはGHCのバージョン7.4.1で確認しています。

モナドトランスフォーマーのモジュールはMark P.Jonesの論文[2]にインスパイアされています。その中には、とても読みやすいMonadプログラミングのイントロダクションはありますが、このチュートリアルほどは実践的ではありません。

この文章は文芸的Haskell(Literate Haskell)のスクリプトからAndres Lo ̈hのlhs2TeXプリプロセッサを使って変換されています。 そのテキストはGHCで実行可能です。 文芸的Haskellのソースファイル Transformers.lhs は著者のウェブサイトhttp://www.grabmueller.de/martin/www/pub/Transformers.en.htmlにあります。

コンピュータを前にしてこのチュートリアルを読むのがベストでしょう。 Haskellの標準ライブラリやモナドトランスフォーマーのライブラリにある、いろいろな関数の説明を調べたり、型を調べたりできるようにです。 このチュートリアルを印刷して、ウェブブラウザでオンラインのライブラリのドキュメントを開いて、Transformersモジュール(あとで説明します)をロードしてghciで対話的に:type(もしくは:t)で型を確認しながら実行してみるのが一番でしょう。

1.1 プログラム例(Example Program)

実行する例として、シンプルなプログラミング言語インタープリタをこのチュートリアルを通して使います。 すべてのコードはTransformersというモジュールに収められ、次のようなコードが頭にあります。

module Transformers where
import Control.Monad.Identity
import Control.Monad.Error
import Control.Monad.Reader
import Control.Monad.State
import Control.Monad.Writer
import Data.Maybe
import qualified Data.Map as Map

Control.Monadで始まるインポートされたモジュールは、その中で定義されたモナドトランスフォーマーを使うときだけ必要となります。 Data.MaybeモジュールはMaybe a型の任意の値を扱うのに便利な関数を定義していて、Data.Mapモジュールは有限のマップを定義します。 これらは、環境(変数-値のマッピング)を小さなインタープリタの中で定義するのに使われます。

次のデータ型がその言語の中でプログラムをモデリングをするのに使われます。

type Name   = String                -- variable names (変数名)
data Exp    = Lit Integer           -- expressions (式)
            | Var Name
            | Plus Exp Exp
            | Abs Name Exp
            | App Exp Exp
            deriving (Show)
data Value  = IntVal Integer        -- values (値)
            | FunVal Env Name Exp
            deriving (Show)
type Env    = Map.Map Name Value    -- mapping from names to values (変数名から値へのマッピング)

Name型は標準のString型のただの別名です。 普遍的な文字列でなく、変数名についての話であることを明確にする時に使われます。 Expデータ型は、整数リテラル・変数・加算・λ式(抽象)・関数適用へのヴァリアントを持っています。 評価されるプログラムはExpデータ型からできていて、結果はValue型です。 Valueは整数か関数(クロージャ)です。 FunValの構成要素であるEnvは、λ抽象が評価される環境です。

モナドトランスフォーマーを用いる具体例は、上に示した小さな言語のインタープリタなので、まずは評価関数をつくることから始めます。 この関数はモナドを使っておらず、ある種の「参照実装」となっています。 インタープリタ関数eval0は、単純です。

eval0 :: Env -> Exp -> Value
eval0 env (Lit i)       = IntVal i
eval0 env (Var n)      = fromJust (Map.lookup n env)
eval0 env (Plus e1 e2)  = let IntVal i1 = eval0 env e1
                              IntVal i2 = eval0 env e2
                          in  IntVal (i1 + i2)
eval0 env (Abs n e)     = FunVal env n e
eval0 env (App e1 e2)   = let val1 = eval0 env e1
                              val2 = eval0 env e2
                          in case val1 of
                            FunVal env' n body -> eval0 (Map.insert n val2 env') body

整数リテラル(Lit)は、Value型に包まれてそのまま自分自身に評価されます。 変数(Var)は、その環境で束縛されている値に評価されます。 fromJust関数はMap.lookup関数がMaybeを返すので必要です。 この関数では、どこにもラムダ式で束縛されていない変数が使われてしまうと、エラーメッセージと共にプログラムは停止します。 加算(Plus)は単純に2つのオペランドを評価して、その和を返します。 加算のオペランドがが片一方でも数値にならなかったら、let式のパターンマッチングは失敗し、やはりエラーメッセージと共にプログラムは終了してしまいます。 抽象(Abs)は、評価される環境にを捉えて関数値に評価されます。 関数適用(App)は、最初に関数と引数を評価し、加算と同じように処理されます。 一番目の式は関数値に評価されなければならず、環境に従ってその内部が評価されます。 ここで使われている関数値を分解しているcase式は、また別のエラーを吐くかもしれません。 このチュートリアルの後の方では、エラーモナドを使ってエラーを扱い、エラーの扱いをもっと強力にしています。

eval0の定義はもう少し短くもできます。例えば、Appの時のlet式は冗長かもしれません。 しかし、ここでの定義は、後で定義されるモナド版にするのが簡単になります。

12 + ((λx -> x)(4+2))

この式は、このインタープリタを試すのにも使えますし、すぐに残りも定義していきます。

exampleExp = Lit 12 `Plus` (App (Abs "x" (Var "x")) (Lit 4 `Plus` Lit 2))

例えば、

> eval0 Map.empty exampleExp

とghciに入力すれば、答えは

IntVal 18

となります。

2 モナドトランスフォーマー(Monad Trasformers)

モナドトランスフォーマーを使う目的は、状態・エラー・環境といった計算の側面をコントロールすることです。 すでにあるプログラムをモナドを使って書きなおすのは少々面倒臭いですが、一度やってしまうとモナドが絡む部分を加えたり、削ったり、変更したりするのは比較的簡単です。

この節では、1.1節のプログラムをモナドを使って書き直し、データ型や関数定義を様々なモナドトランスフォーマーの型や関数を使って徐々に拡張していきます。

2.1 モナドスタイルに(Converting to Monadic Style)

モナドトランスフォーマーを使うには、関数をモナドスタイルで表現しなければなりません。 それはつまり、逐次処理をdo記法を使ったモナド操作で書き、関数の結果を示すためにreturn関数を使う必要があるということです。

まず、評価装置が定義されるモナドを定義します。 下のEval1 aIdentity a型の別名として定義します。Identityは、Control.Monad.Identityからインポートされてモナドで、想像しうる限り一番単純なモナドかもしれません。 Identityは、標準的なreturnや(>>=)をモナド操作の構築のために定義していて、runIdentity関数をそのような操作を実行するために追加で定義しています。 それ以外にはIdentityモナドは何もしません。 ある意味で、このモナドを「基礎」として使い、周りを別のモナドで包むこともできます。 可読性のため、ただrunIdentityを呼ぶためのrunEval1も定義しています。 runEval1はrunIdentityを呼び出すだけです。

type Eval1 a = Identity a
runEval1 :: Eval1 a -> a
runEval1 ev = runIdentity ev

Eval1モナドをもとにeval0関数をeval1として書きなおします。

eval1 :: Env -> Exp -> Eval1 Value
eval1 env (Lit i)       = return $ IntVal i
eval1 env (Var n)       = maybe (fail ("undefined variable: " ++ n)) return $ Map.lookup n env
eval1 env (Plus e1 e2)  = do IntVal i1 <- eval1 env e1
                             IntVal i2 <- eval1 env e2
                             return $ IntVal (i1 + i2)
eval1 env (Abs n e)     = return $ FunVal env n e
eval1 env (App e1 e2)   = do val1 <- eval1 env e1
                             val2 <- eval1 env e2
                             case val1 of
                                FunVal env' n body ->
                                    eval1 (Map.insert n val2 env') body

まず注目すべきことは、LitとAbsの場合に結果を表すためにreturn関数を使っていることです。 (($)演算子は結合順位が低い関数適用で、主に丸括弧()を省くに使われます。) 次に、Varの場合にはfromJustはもう必要ありません。 これは、Map.lookupはどんなモナドの中でもfail関数を呼ぶだけで動くようになっていて、ここではこれがうまいこと当てはまるからです。 (Identityモナドのfail関数は例外を投げる一方、Maybeモナドのfail関数はNothingを返すので、異なるエラーメッセージが現れます。)

PlusやAppの場合は内部の式をdo記法で評価し、結果を変数に束縛しています。 Plusでは結果はreturnを使って返されますが、Appでは関数値は上のeval0関数のようにさらに識別されます。

このインタープリタを試すには、eval1をサンプルの式exampleExpに適用して得られたモナドのアクションを評価する必要があります。 これは前に定義したrunEval1を呼べば大丈夫です。

runEval1 (eval1 Map.empty exampleExp)

とすれば、

IntVal 18

となります。

要約すれば、return関数を使って関数の結果を返すことと、do記法や(>>=)や(>>)関数をつかってモナドアクションの逐次を行うことの2つからモナドへの変換は成り立っています。


NOTE

eval1の型は、以下のように一般化できます。

eval1 :: Monad m => Env -> Exp -> m Value

これは、returnと、do記法に隠された(>>=)以外には、どんなモナド操作も行っていないためです。 こうすればどんなモナドの文脈でもeval1を使うことができ、

runEval1 (eval1 Map.empty exampleExp)

とする代わりにghciで

eval1 Map.empty exampleExp

と書けます。 これは、IOモナドの内部で式を実行します。インタープリタは内部的にprint関数を使っていますが、この関数はIOモナドの内部でしか使えないためです。 これは嬉しいこともありますが、特定のモナドに固有の操作を使うことが多いでしょうし、特定のモナドに操作は縛られてしまいます。


2.2 エラー処理を加える(Adding Error Handling)

今まで見てきたように、現状の評価関数は部分的(partial)です。 例えば束縛されていない変数や型エラーがある式など、入力によってはエラーメッセージと共に止まってしまいます。 (訳注: 部分関数については、Partial Function Considered Harmfulが参考になります)

ローカルのモナドトランスフォーマーライブラリにあるErrorTモナドトランスフォーマーを使えば、Eval1モナドを基にしてEval2へ拡張できます。

type Eval2 a = ErrorT String Identity a

ErrorTのString型引数は例外の型で、エラーの状態を示すために使われる値です。 ここでは簡単のためにStringを使いますが、実際の実装ではコンパイラだとソースコードの位置だとか、ウェブアプリケーションだとタイムスタンプだとかがあると良いかもしれません。

Eval2モナド内での計算を実行する関数は、2つ異なる点があります。 ひとつ目は評価の結果がEither String a型で、Left sだとエラーが起きたことをエラーメッセージsで示し、Right rだと評価が成功したことを結果rで表します。 二つ目は、runErrorT関数を与えられた計算に対して呼び出し、Identityの計算が返され、今度はそれがrunIdentityを使って評価されるということです。

runEval2 :: Eval2 a -> Either String a
runEval2 ev = runIdentity (runErrorT ev)

さてもうeval1関数の型を単純に書き換えることができて、次のバージョン(eval2a)を示します。

eval2a :: Env -> Exp -> Eval2 Value
eval2a env (Lit i)      = return $ IntVal i
eval2a env (Var n)      = maybe (fail ("undefined variable: " ++ n)) return $ Map.lookup n env
eval2a env (Plus e1 e2) = do IntVal i1 <- eval2a env e1
                             IntVal i2 <- eval2a env e2
                             return $ IntVal (i1 + i2)
eval2a env (Abs n e)    = return $ FunVal env n e
eval2a env (App e1 e2)  = do val1 <- eval2a env e1
                             val2 <- eval2a env e2
                             case val1 of
                                FunVal env' n body
                                    -> eval2a (Map.insert n val2 env') body

このバージョンは上で定義されたrunEval2関数を使って実行できます。 この関数をサンプルの式に適用すると、結果はRight構築子に包まれている点のみが変わっています。

runEval2 (eval2a Map.empty exampleExp) => Right (IntVal 18)

しかし残念なことに、正しくない式が与えられるとErrorTトランスフォーマーのエラー報告は使われません。 もっと有用なエラーメッセージを吐くためには改良が必要です。

eval2b :: Env -> Exp -> Eval2 Value
eval2b env (Lit i)      = return $ IntVal i
eval2b env (Var n)      = maybe (fail ("undefined variable: " ++ n)) return $ Map.lookup n env
eval2b env (Plus e1 e2) = do e1' <- eval2b env e1
                             e2' <- eval2b env e2
                             case (e1', e2') of
                                (IntVal i1, IntVal i2) -> return $ IntVal (i1 + i2)
                                _                      -> throwError "type error"
eval2b env (Abs n e)    = return $ FunVal env n e
eval2b env (App e1 e2)  = do val1 <- eval2b env e1
                             val2 <- eval2b env e2
                             case val1 of
                                FunVal env' n body
                                    -> eval2b (Map.insert n val2 env') body
                                _   -> throwError "type error"

これで、正しくない式を評価しようとすると、Left構築子に包まれたエラーメッセージが出ます。 そして、評価結果に対してパターンマッチングをすることで、通常の結果とエラーの結果を区別することができます。

runEval2 (eval2b Map.empty (Plus (Lit 1) (Abs "x" (Var "x")))) =>
    Left "type error"

(訳注: 原文では runEval2 (eval2a Map.empty (Plus (Lit 1) (Abs "x" (Var "x")))) となっているが、著者の意図は恐らくeval2aでなくeval2b)

しかしちょっと待ってください! Map.lookupについてはどうでしょう? Nothingを返すかどうかを確かめて、適切なエラーメッセージを生成するべきではないでしょうか? 前述したとおり、Map.lookupは任意のモナドで結果を返しますし、Control.Monad.Errorモジュールはすぐに動くように必要な定義を提供しています。

runEval2 (eval2b Map.empty (Var "x")) =>
    Left "Data.Map.lookup: Key not found"

(訳注: containers-0.5.2.1の実際のData.Map.lookupの定義は、Maybeモナドを返すようになっている。なので、上記のエラーメッセージは、実際には Left "undefined variable: x" となる)

eval2b関数をもうちょっとよく調べてみれば、do式の内部のモナド結合ではパターンマッチングが失敗したときにfail関数を呼び出すということをうまく使うと、もっと短く(良く?)できることがわかります。 そして、今まで見てきたように、fail関数は思ったとおりに動いてくれます。

eval2c :: Env -> Exp -> Eval2 Value
eval2c env (Lit i)      = return $ IntVal i
eval2c env (Var n)      = maybe (fail ("undefined variable: " ++ n)) return $ Map.lookup n env
eval2c env (Plus e1 e2) = do IntVal i1 <- eval2c env e1
                             IntVal i2 <- eval2c env e2
                             return $ IntVal (i1 + i2)
eval2c env (Abs n e)    = return $ FunVal env n e
eval2c env (App e1 e2)  = do FunVal env' n body <- eval2c env e1
                             val2               <- eval2c env e2
                             eval2c (Map.insert n val2 env') body

この関数の難点は、エラーメッセージが"pattern match failure"(パターンマッチング失敗)としか言わないことで、どうしてパターンマッチングが失敗したのかについて具体的な情報は何もないということです。 ですので、もっと良いエラーメッセージが欲しいなら、自分でthrowErrorをする方が良いです。 これがエラー処理評価をする最終バージョンです。

eval2 :: Env -> Exp -> Eval2 Value
eval2 env (Lit i)       = return $ IntVal i
eval2 env (Var n)       = case Map.lookup n env of
                            Nothing  -> throwError ("unbound variable: " ++ n)
                            Just val -> return val
eval2 env (Plus e1 e2)  = do e1' <- eval2 env e1
                             e2' <- eval2 env e2
                             case (e1', e2') of
                                (IntVal i1, IntVal i2)
                                    -> return $ IntVal (i1 + i2)
                                _   -> throwError "type error in addition"
eval2 env (Abs n e)     = return $ FunVal env n e
eval2 env (App e1 e2)   = do val1 <- eval2 env e1
                             val2 <- eval2 env e2
                             case val1 of
                                FunVal env' n body
                                    -> eval2 (Map.insert n val2 env') body
                                _   -> throwError "type error in application"

NOTE

Control.Monad.ErrorモジュールはthrowErrorで生じたエラーを捕まえるように、別の関数も提供しています。 それが、catchError :: m a -> (e -> m a) -> m aで、任意のエラーモナドに使えます。 局所的なエラー処理にもエラーを上位に渡すことにも使えます。


2.3 環境を隠す(Hiding the Environment)

評価関数の定義をもっといいものにする一つの方法は、すべての関数定義と呼び出しから環境を隠すことです。 環境が展開される場所は一カ所(関数適用)だけ、実際に使われる場所は二ヶ所(変数とラムダ式)だけなので、他の場所では環境を隠せばコードの量を減らすことができます。 これはリーダーモナドを実装するためにReaderTモナドトランスフォーマーを加えれば実現できます。 Readerモナドは、値をその下のすべての計算に渡します。 この値は内側の計算から読むことができ、入れ子になった計算の中では改変することもできます。 状態(State)モナド(2.4節で紹介されます)と異なり、カプセル化された計算は上位の計算で使われた値を改変することができません。

以前のモナド単にをReaderT構築子で包むことから始めます。

type Eval3 a = ReaderT Env (ErrorT String Identity) a

実行関数runEval3は、初期環境を与える必要があるので少し変更しなければなりません。 評価関数から環境引数を削ることが目的です。

runEval3 :: Env -> Eval3 a -> Either String a
runEval3 env ev = runIdentity (runErrorT (runReaderT ev env))

eval3 :: Exp -> Eval3 Value
eval3 (Lit i)       = return $ IntVal i
eval3 (Var n)       = do env <- ask
                         case Map.lookup n env of
                            Nothing  -> throwError ("unbound variable: " ++ n)
                            Just val -> return val
eval3 (Plus e1 e2)  = do e1' <- eval3 e1
                         e2' <- eval3 e2
                         case (e1', e2') of
                            (IntVal i1, IntVal i2)
                                -> return $ IntVal (i1 + i2)
                            _   -> throwError "type error in addition"
eval3 (Abs n e)     = do env <- ask
                         return $ FunVal env n e
eval3 (App e1 e2)   = do val1 <- eval3 e1
                         val2 <- eval3 e2
                         case val1 of
                            FunVal env' n body
                                -> local (const (Map.insert n val2 env')) (eval3 body)
                            _   -> throwError "type error in application"

サンプルを実行するなら、以下のように評価してください。

runEval3 Map.empty (eval3 exampleExp)

現在の環境が必要になる場所では、Readerモナドの隠れた状態からask関数を使って引き出します。 関数適用の場合では、local関数が再帰的呼び出しの環境を変更するのに使われています。 localは(r -> r) -> m a -> m a型を持っていて、現在の環境から、第二引数にある入れ子になった計算で使われる環境へのマップをする関数を渡す必要があります。 この場合では、入れ子になった環境は現在の環境に直接依存していないので、const関数に渡すだけです。


NOTE

askに加え、asks関数が予め定義されていて環境から値へとマッピングする関数を取ります。 これは、レコードセレクター関数(record selector function)にasksを適用して環境のそれぞれの構成要素を取り出すのに使うこともできます。 (訳注:レコードセレクター関数とは、データ型をrecord syntaxで定義した際にコンパイラが自動的に作るフィールドの値を取得する関数のことです。)


2.4 状態を加える(Adding State)

重要なモナドの応用例として、純粋関数型のプログラムに変更可能(mutable)な状態を可能にすることが挙げられます。 これはStateモナドを用いればよく、初期状態の設定・現在の状態の問い合わせ・変更といった操作を提供してくれています。

例として、このインタープリタにプロファイリング機能を付け足したいとしましょう。 最も内側のモナド(Identity)をStateT構築子で包んで新しいモナドを定義します。 (StateモナドErrorモナドに関しては、後で見るように構築子の順番が問題になります。) 例では単純な整数値を状態として保持しますが、どんなデータ型の値でも可能です。 通常は、目下の仕事に必要十分な状態を、記録として保持することになります。

type Eval4 a = ReaderT Env (ErrorT String (StateT Integer Identity)) a

runEval4関数の返り値の型は変わります。 最終的な状態が評価結果(エラーか計算値)と一緒に返されるからです。 さらに、初期状態を追加の引数で渡し、例えば別の計算の最後の状態から再度計算を始めるなどができるように、柔軟性を持たせています。

runEval4 :: Env -> Integer -> Eval4 a -> (Either String a, Integer)
runEval4 env st ev = runIdentity (runStateT (runErrorT (runReaderT ev env)) st)

単純な例として、評価のステップ数を数えるだけにしたいと思います。 つまり、eval4関数を呼んだ回数です。 状態の変更は、すべて小さな補助的関数tickの中で起き、隠された状態を計算から取り出し、カウンターを増やして、状態を戻します。 この先の節で再利用するつもりなので、もちろんtickの型はEval4 ()ではありません。 ですので、中でtickが使われるモナドは状態モナド(訳注:この場合MonadState型クラスのこと)で、そのモナドの中で操作される状態は(+)演算子を使えるように数値にすると言うにとどめます。

tick :: (Num s, MonadState s m) => m ()
tick = do st <- get
          put (st + 1)

それぞれの場合でtick関数の呼び出しを加えれば、適用の回数を数えることができます。

eval4 :: Exp -> Eval4 Value
eval4 (Lit i)       = do tick
                         return $ IntVal i
eval4 (Var n)       = do tick
                         env <- ask
                         case Map.lookup n env of
                            Nothing  -> throwError ("unbound variable: " ++ n)
                            Just val -> return val
eval4 (Plus e1 e2)  = do tick
                         e1' <- eval4 e1
                         e2' <- eval4 e2
                         case (e1', e2') of
                            (IntVal i1, IntVal i2)
                                -> return $ IntVal (i1 + i2)
                            _   -> throwError "type error in addition"
eval4 (Abs n e)     = do tick
                         env <- ask
                         return $ FunVal env n e
eval4 (App e1 e2)   = do tick
                         val1 <- eval4 e1
                         val2 <- eval4 e2
                         case val1 of
                            FunVal env' n body
                                -> local (const (Map.insert n val2 env')) (eval4 body)
                            _   -> throwError "type error in application"

サンプルを評価すると、

(Right (IntVal 18), 8)

と出ます。これは評価が成功して整数18を返し、簡約が8ステップだったということを表しています。


NOTE

Eval4モナドの型を次のように変える(StateTとErrorTを入れ替えた)と、モナドの解釈が変わります。

type Eval4' a = ReaderT Env (StateT Integer (ErrorT String Identity)) a

結果(エラーか否か)と状態を返す代わりに、エラーか結果と最終的な状態かを返します。 これは対応する実行関数の型からも分かるでしょう。

runEval4' :: Env -> Integer -> Eval4' a -> (Either String (a, Integer))
runEval4' env st ev = runIdentity (runErrorT (runStateT (runReaderT ev env) st))

最終的な状態には関与しないので、Readerモナドトランスフォーマーの位置は問題にはなりません。



NOTE

Stateモナドgets関数も提供しており、結果を返す前に状態に対して関数を適用します。 内部状態に関数を適用することによって状態を変更するmodify関数もあります。


2.5 ログを加える(Adding Logging)

ここで述べる道具箱にある最後のモナドトランスフォーマーWriteTです。 ある意味ReaderTの対になるものです。WriterTが提供する関数は、渡された値を用いるものではなく、計算結果に値を追加するものだからです。

type Eval5 a = ReaderT Env (ErrorT String
                           (WriterT [String] (StateT Integer Identity))) a

StateTの場合と同様に、結果を出力するものなのでWriterTはErrorTと干渉します。 ErrorTとWriterTの順番によって、エラーが起きたときに、結果が(訳注:Writerモナドの)値を返すかどうかが変わります。 書き出される値、は文字列のリストです。 WriterTモナドトランスフォーマーのドキュメントを読むと、書きだされた値の型はモノイド(Monoid)型クラスのメンバーに制限されることがわかるでしょう。 このことは、このクラスのメソッドは内部的に初期値を構成したり、書き出される値を合成したりするのに使われるため必要なことです。

実行関数は先ほどと同じように拡張されます。

runEval5 :: Env -> Integer -> Eval5 a -> ((Either String a, [String]), Integer)
runEval5 env st ev =
    runIdentity (runStateT (runWriterT (runErrorT (runReaderT ev env))) st)

評価関数では、評価中に遭遇した変数名を書き出すことによって、Writerモナドの使い方を説明しています。

eval5 :: Exp -> Eval5 Value
eval5 (Lit i)   = do tick
                     return $ IntVal i
eval5 (Var n)   = do tick
                     tell [n]
                     env <- ask
                     case Map.lookup n env of
                        Nothing  -> throwError ("unbound variable: " ++ n)
                        Just val -> return val
eval5 (Plus e1 e2) = do tick
                        e1' <- eval5 e1
                        e2' <- eval5 e2
                        case (e1', e2') of
                            (IntVal i1, IntVal i2)
                                -> return $ IntVal (i1 + i2)
                            _   -> throwError "type error in addition"
eval5 (Abs n e)   = do tick
                       env <- ask
                       return $ FunVal env n e
eval5 (App e1 e2) = do tick
                       val1 <- eval5 e1
                       val2 <- eval5 e2
                       case val1 of
                        FunVal env' n body
                            -> local (const (Map.insert n val2 env')) (eval5 body)
                        _   -> throwError "type error in application"

2.6 IOはどうすんの?(What about I/O?)

これまでのところ、ある重要な面を考慮していません。入力と出力です。 どのようにしてこれまでに開発してきたモナドの定義に、入出力を導入すればいいでしょうか。 IOモナドトランスフォーマーを定義することはできません。 なぜなら、HaskellのIO操作の実行は他の関数やモナドに勝手に入れ子にしてはならず、IOモナドでのみ可能になっているからです。 幸運なことに、モナドトランスフォーマーのライブラリは、私たちが組み上げてきたものに簡単にIO操作を導入する下地を提供してくれています。 単にIdentityの代わりにIOを使えばいいのです! これは、Identityが基になるモナドで、今まで見てきたように、このモナドのアクションを評価するrunIdentity関数は、いつでも一番最後に適用されていたからです。

type Eval6 a = ReaderT Env (ErrorT String
                           (WriterT [String] (StateT Integer IO))) a

runEval6が返す型は、IO構築子によって包まれています。 Eval6の計算を実行することは直接的に結果を出すのではなく、結果を得るには実行しなければならないIO計算を返します。

runEval6 :: Env -> Integer -> Eval6 a -> IO ((Either String a, [String]), Integer)
runEval6 env st ev
    = runStateT (runWriterT (runErrorT (runReaderT ev env))) st

eval6関数では、ちょっとしたひと手間でIO操作を行えます。 それには、liftIO関数を使って操作を呼び出す必要があり、これでIO計算を現在実行中のモナドに持ち上げることができます。 例として、整数定数が評価される度にプリントすることにします。(これが良い方法だとは思いませんが、要点を説明できますし、良いデバッグのテクニックになることもあります。)

eval6 :: Exp -> Eval6 Value
eval6 (Lit i)      = do tick
                        liftIO $ print i
                        return $ IntVal i
eval6 (Var n)      = do tick
                        tell [n]
                        env <- ask
                        case Map.lookup n env of
                            Nothing  -> throwError ("unbound variable: " ++ n)
                            Just val -> return val
eval6 (Plus e1 e2) = do tick
                        e1' <- eval6 e1
                        e2' <- eval6 e2
                        case (e1', e2') of
                            (IntVal i1, IntVal i2)
                                -> return $ IntVal (i1 + i2)
                            _   -> throwError "type error in addition"
eval6 (Abs n e)    = do tick
                        env <- ask
                        return $ FunVal env n e
eval6 (App e1 e2)  = do tick
                        val1 <- eval6 e1
                        val2 <- eval6 e2
                        case val1 of
                            FunVal env' n body
                                -> local (const (Map.insert n val2 env')) (eval6 body)
                            _   -> throwError "type error in application"

3 結論(Conclusion)

モナドトランスフォーマーは関数型プログラマーの持てる強力なツールです。 このチュートリアルでは、現在のHaskellの実装で利用できるモナドトランスフォーマーと、簡単なインタープリタを作るのにそれらをどうやって組み合わせるかを紹介しました。

ここでは、現在実装されているモナドトランスフォーマーを全てはカバーしていません。(例えば継続やリストのモナドトランスフォーマー) もっと情報を得るために、Haskellのウェブサイトにあるライブラリのドキュメントを読むこともおすすめします。

モナドトランスフォーマーを使うことで、今のアプリケーションでやりたいことを、一枚岩でお手製のモナドにまとめ上げ、様々なアプリケーションに特化したモナドをいとも簡単に作り出すことができます。

Happy hacking in Haskell!!

References

  • [1] GHC Developers. Glasgow Haskell Compiler Homepage. Available from: http://www. haskell.org/ghc, 2008. Last visited: 2008-10-07.
  • [2] Mark P. Jones. Functional programming with overloading and higher-order polymorphism. In First International Spring School on Advanced Functional Programming Techniques, vol- ume 925 of Lecture Notes in Computer Science, pages 97–136, B ̊astad, Sweden, May 1995. Springer-Verlag.