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

関数getPasswordとそれを利用するコードを簡潔に書くために、IOモナドにMaybeモナドの特性を与えるモナドトランスフォーマーを定義します。これを、モナドトランスフォーマーの慣例的な名付け方に従い、最初に与える特性を持つモナドの名前＋Tとし、MaybeTと呼びます。

MaybeTは、m (Maybe a)のラッパーで、mにはどのようなモナドも入ることが出来ます。（ここではIOに注目します。）

newtype (Monad m) => MaybeT m a = MaybeT {runMaybeT :: m (Maybe a)}

アクセサ関数runMaybeTを使うことによってMaybeTのなかに隠れた中身にアクセスできます。

モナドトランスフォーマー自身もモナドであるため、MaybeT mをMonadクラスのインスタンスとして置く必要があります。

instance Monad m => Monad (MaybeT m) where
	return = MaybeT . return . Just

returnは値をとって、それをJustによってMaybeとなり、普通のreturnによってモナドmにし、MaybeTコンストラクタを適用します。読みにくいですが、

return = MaybeT . return . return

でも大丈夫です。
それでは>>=演算子の方を見ていきます。

x >>= f = MaybeT $ do
	maybe_value <- runMaybeT x
	case maybe_value of
		Nothing -> return Nothing
		Just value -> runMaybeT $ f value

(>>=)演算子の定義をみることで、トランスフォーマーがどうして動くのか、どのようにMaybeの値を展開するのか、NothingまたはJustの値を受け取った時m Nothingまたはm (Just value)のようにMaybeTの中に包んでいくのかが理解できると思います。

doブロックの中でアクセサrunMaybeTがあるのに、MaybeTコンストラクタがdoブロックの前にあることが不思議になるかもしれません。しかし、>>=演算子を定義していないため、doブロックはMaybeT mのなかではなく、モナドmの中になくてはなりません。

技術的には、しなくてはならないことはこれで全部です。しかし、MaybeTを幾つかの他のクラスのインスタンスにしておくと便利です。

instance Monad m => MonadPlus (MaybeT m) where
	mzero = MaybeT $ return Nothing
	mplus x y = MaybeT $ do
		maybe_value <- runMaybeT x
		case maybe_value of
			Nothing -> runMaybeT y
			Just value -> runMaybeT x

instance MonadTrans MaybeT where
	lift = MaybeT . (liftM Just)

MonadTransは関数liftを宣言しており、この関数はmモナドからMaybeT mモナドに持ってくるときに便利な関数ですので、MaybeT mモナドの中のdoブロック内で用いることが出来ます。

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

ここまでで、モナドがどういうもので、IOモナドは不純な計算のため、Maybeは失敗するかもしれない計算のために、…というように、どのように使われるのかが理解できたのではないかと思います。

実際の作業の中で、複数のモナドの特性を扱いたい場合があります。もちろん、IO (Maybe a)みたいなことを書いて使うことも出来ますが、それでは値を取り出すとき、doブロックの中でパターンマッチングを行わなくてはなりません。モナドのちからを使えば、それすら回避することが出来ます。

ということで、これからしばらくモナドトランスフォーマーについて書いていきます。これは特別な型で、モナドに適用した時、新たな合成されたモナドを生成します。このモナドはそのどちらの性質も持ち合わせることになります。

IT業界に生きる上で、ユーザーにパスワードを強固なものにするようにすすめるプログラムという、よくある問題を例にして考えてみます。一般的な解決方法として、ユーザがパスワードを設定する時、そのパスワードが最低限の長さをもち、かつ１文字以上のアルファベット、１文字以上の数値、などといった制限をクリアしたもののみ通すというものがあります。
ユーザからパスワードを受け取る関数は以下のように書くことができるでしょう。

getPassword :: IO (Maybe String)
getPassword = do
	s <- getLine
	if isValid s then return $ Just s
	else return Nothing

getPasswordが実行された時、かならず同じ結果になると決まっているわけではないので、IOモナドになり、また、パスワードが制限に引っかかった場合Nothingが返ってくるようにしたいのでMaybeモナドになります。
isValidはわりとどうでもいいのですが、以下のようにしておきます。

isValid :: String -> Bool
isValid s = length s >= 8 && any isAlpha s && any isNumber s && any isPunctuation s

モナドトランスフォーマーを使う利点は、getPasswordを綺麗に書くというためではなく（もちろんなりますが）、むしろコードの利用を簡単にするために使われます。以下はモナドトランスフォーマーを利用しない場合の、getPasswordを使った関数です。

askPassword :: IO ()
askPassword = do
	putStrLn "Insert your new password: "
	maybe_value <- getPassword
	if isJust maybe_value
		then do
			putStrLn "Storing in database..."
			--...
	else ....

maybe_valueが必要になる上、パスワードが大丈夫なのかどうかなどを改めてチェックする必要があります。
モナドコンビネータを使えば、パターンマッチを使用することなく１度でパスワードを生成することができます。この例ではありがたみがいまいちわからないかもしれませんが、追々複雑な例を見ていきます。

Haskellのモナド３(5)

モノイドについて知らないなら、この記事がわからなくても問題無いです。

モノイドは、幾つかの公理を満たす、単位元（ゼロ）と２項演算（プラス）の２つのメソッドがあるクラスです。

class Monoid m where
	mempty :: m
	mappend :: m -> m -> m

例えば、リストはシンプルなモノイドです。

instance Monoid [a] where
	mempty = []
	mappend = (++)

宣言のところで、[]ではなく[a]となっていることに気づいたでしょうか。モノイドはなんらかのコンテナである必要はありません。例えば、整数（実際には自然数もですが）もモノイドを形成することができます。

newtype AdditiveInt = AI Int
newtype MultiplicativeInt = MI Int

instance Monoid AddictiveInt where
	mempty = AI 0
	AI x `mappend` AI y = AI (x + y)

instance Monoid MultiplicativeInt where
	mempty = MI 1
	M1 x `mappend` MI y = MI (x * y)

Monoidは、MonadPlusのインスタンスと非常に似ています。どちらもゼロと加算の機能をもち、当然ですがMonadPlusはMonoidのサブクラスとすることが出来ます。

instance MonadPlus m => Monoid (m a) where
	mempty = mzero
	mappend = mplus

しかし、これらが同じ層で働くことはありません。先程も言いましたが、モノイドがなんらかのコンテナとなる必要はありません。モノイドはkind *を持ちますが、MonadPlusはMonadであるため、kind * -> *だからです。

Haskellのモナド３(4)

mplusとmzeroの他にも、いくつか知っておくべき関数があります。

msum
MonadPlusのインスタンスを扱っている時に、モナドのリスト[Maybe a]、つまり[[a]]を受け取ってそれをmplusで折りたたんでいくという作業をよく行います。msumがまさにそれです。

msum :: MonadPlus m => [m a] -> m a
msum = foldr mplus mzero

これは、リストの結合の一般化と考えれば良いです。実際、リストモナドに対するmsumはまさにリストの結合となります。Maybeモナドでは、リスト中の最初のJust xを見つけ、もしJust xが含まれていない場合、Nothingを返します。

guard
guardは、非常に便利な関数で、おそらく知らず知らずのうちに使ったことがあるかと思います。これはリスト内包表記の中でも用いられます。リスト内包表記をリストモナドに戻して書くと、以下のようになりますね。

pythags = [(x, y, z) | z <- [1..], x <- [1..z], y <- [x..z], x^2 + y^2 == z^2]

これは以下のように書きなおすことが出来ました。

pythags = do
	z <- [1..]
	x <- [1..z]
	y <- [x..z]
	guard (x^2 + y^2 == z^2)
	return (x, y, z)

guardの定義は以下のようになっています。

guard :: MonadPlus m => Bool -> m ()
guard True = return ()
guard False = mzero

具体的には、guardは引数がFalseであるなら呼んだdoブロックにmzeroを返します。MonadPlusの法則として、

mzero >>= hoge  == mzero

というのがありましたね。doブロックは>>=演算の塊ですので、mzeroが処理の中に入るとdoブロック全体がmzeroとなります。

もう少し説明するために、上のピタゴラス関数を拡張して、リストモナドの特別なguardを考えてみます。まず、以下がリストモナド用のguardです。

guard :: Bool -> [()]
guard True = [()]
guard False = []

guardは値を弾きます。例えば、ピタゴラス関数では、「x^2 + y^2 = z^2でない」すべての値を弾いてほしいです。先ほどのdo構文ピタゴラス関数を展開したものをみてみましょう。

pythags =
	[1..] >>= \z ->
	[1..z] >>= \x ->
	[x..z] >>= \y ->
	guard (x^2 + y^2 == z ^2) >>= \_ ->
	return (x, y, z)

(>>=)とreturnをリストモナドのそれに置き換えると、以下のようになります。

pythags =
	let ret x y z = [(x, y, z)]
		gd z x y = concatMap (\_ -> ret x y z) (guard $ x^2 + y^2 == z^2)
		doY z x = concatMap (gd z x) [x..z]
		doX z    = concatMap (doY z) [1..z]
		doZ       = concatMap (doX ) [1..]
	in doZ

もし与えられた引数がFlaseとなったとき、guardがカラリストを結果として返すことに気をつけてください。空リストに対してマッピングした場合、どのような関数を渡しても空リストにしかなりません。そのため、gdの中、guardによって作られた空リストはgdに結び付けられ、結果retは空リストとなります。

なぜこれが大切なのかは、リスト計算というものが木のようなものだと考えればわかります。ピタゴラスの三角形を探索するとき、まずzを決め、そこから派生する答えかもしれない可能性（木）の中、xを決め、そのxから派生する木からyを決める必要があります。ですので、このようなずになるかと思います。

start
	|__________________________________.....
z	1				2
	|				|
	|				...
	|
	|____....    ____________________.....
	|				|
x  1				1
	|
	|_________....
	|				|
y	1				1

x, y, zの組み合わせそれぞれが可能性を表しています。関数がこの木を評価し終わった時、木の下の方から結果をつなげていきます。結果が空リストであれば、この結合作業に全く影響しないので、結果演算が成功します。

Haskellのモナド３(3)

MonadPlusのインスタンスは、モナドのインスタンスがモナド則を満たす必要があるのと同様に、いくつかの法則を満たさなくてはなりません。残念ながら、これらの法則はまだ確定していません。ただ、確実に必要なのが、mzeroとmplusがモノイドを形成することで、すなわち、

mzero `mplus` m = m
m `mplus` mzero = m
m `mplus` (n `mplus` o) = (m `mplus` n) `mplus` o

Control.Monadでは、次の法則が追加されています。

mzero >>= f = mzero
m >> mzero = mzero

Haskell Wikiでは他に以下が追加されています。

(m `mplus` n) >>= k = (m >>= k) `mplus` (n >>= k)

実際にはこの他にもいろいろな法則があるため、IOがMonadPlusとして扱われているようなモナドを見るかもしれません。All About MonadsやHaskell WikiのMonadPlusあたりを見ればそのへんの情報が載っています。

Haskellのモナド３(2)

入力をパースする伝統的な方法として一つづつ文字を消費する関数を書くという方法があります。すなわち、文字列をとって、それを切り離して、もしそれの先頭が予め決めた条件（例えば、大文字しか受け付けないという条件）を満たすならそれらを順次消費していきます。しかし、もし文字列の先頭がその条件を満たさないならば、パースは”失敗”しているといい、したがって、パーサはMaybeを用いて作られることが多いです。

ここではmplusを用いて２つのパーサを並行して実行しています。つまり、もし最初のパーサが成功したらその結果を使い、もし失敗したら、２つ目の結果を用います。どちらのパーサも失敗した場合、全体としてNothingを返します。

-- 入力の中の数値を消費し、パースされた数値を返します。do記法を使って、どの段階で失敗してもMaybeモナド（Nothing）が返るようになっています
digit :: Int -> String -> Maybe Int
digit i s
	| i > 9 || i < 0 = Nothing
	| otherwise = do
		let (c:_) = s
		if read [c] == i then Just i else Nothing
-- バイナリ文字（0, 1）を消費します
binChar :: String -> Maybe Int
binChar s = digit 0 s `mplus` digit 1 s

Haskellのモナド３(1)

モナドについて学ぶうちに気づかれたかもしれませんが、どちらも計算結果の個数を表現するという意味でMaybeモナドとリストモナドは結構似ています。 すなわち、Maybeモナドを使用して計算が失敗する可能性（０個または１個の結果）を、リストモナドを使用して計算結果が０個以上の正しい結果を返す可能性（空リストが失敗、それ以外が正しい結果）を表現することが出来ます。

これらのモナドの計算を２つ与えられたとき、これらを結合するのも面白いかもしれません。例えば、正しい結果を”すべて”みつけたいとき、すなわち、２つの正しい結果としてのリストが与えられたとして、すべての正しい結果をみつけたいとき、単純にリストを結合すればいいですね。こういった形で結合できるということは、foldを使った折りたたみのときに”リストにとっての０”、つまり空リストを扱う上などで便利だったりします。

この２つの機能を型クラスとして用意します。

class Monad m => MonadPlus m where
	mzero :: m a
	mplus :: m a -> m a -> ma

Maybeモナドとリストモナドのインスタンス定義が以下になります。

instance MonadPlus [] where
	mzero = []
	mplus = (++)

instance MonadPlus Maybe where
	mzero = Nothing
	Nothing `mplus` Nothing = Nothing  -- 0+0=0
	Just x `mplus` Nothing = Just x  -- 1+0=1
	Nothing `mplus` Just x = Just x  -- 0+1=1
	Just x `mplus` Just y = Just x  -- 1+1=2、ただしMaybeモナドはひとつしか結果を取れないので２つ目のを無視する

もしControl.Monad.Errorをインポートした場合、(Either e)もインスタンスとなります。

instance (Err e) => MonadPlus (Either e) where
	mzero = Left noMsg
	Left _ `mplus` n = n
	Right x `mplus` _ = Right x

Either eはMaybeのように、「失敗するかもしれない計算」を表していますが、失敗した場合、計算の中にエラーメッセージを含めることが出来ます。一般的に、Left sはエラーメッセージsとともに計算が失敗したことを伝え、Right xはxという結果とともに計算が成功したことを示しています。