QAで学ぶMonad
この記事は、Monad でつまづいた Haskeller のための Monad 再入門です。
Monadとは何ですか？
Monad とは、単なる型クラスの一つです。難しいという風評もありますが、それ以上でもそれ以下でもありません。
この型クラスのメソッドは、return と >>= です。
class Monad m where (>>=) :: m a -> (a -> m b) -> m b return :: a -> m a
つまり、以下を満たす型の集合が Monad です。
- m a で表現できるように一つの型変数を格納するコンテナ型
- >>= と return を実装
return は新しいコンテナを作り、>>= は二つのコンテナを合成します。
Monad のインスタンスは失敗系と状態系に大別できます。以下に代表的なインスタンスを示します。
- 失敗系: Maybe、[] (リスト)
- 状態系: Parser、IO
Monad の不幸は、Maybe 以外が分かりにくいことです。
単なる型クラスなのに、どうしてこうも騒がれるのでしょうか？
それは、do という特殊な書式が使えること、副作用を起こすには IO という Monad をさけて通れないことが理由でしょう。 do や IO については後述します。
単なる型クラスと言われてもやっぱり分かりません
Monad を理解するには、まず Functor と Applicative という型クラスを理解するとよいでしょう。Functor を特殊化すると Applicative になり、Applicative を特殊化すると Monad になります。
では、Functor とは何ですか？
Functor とは、fmap というメソッドを提供する型クラスです。
class Functor f where fmap :: (a -> b) -> f a -> f b
リストに特化している fmap が map です。map なら分かりますよね？
> map (+1) [1,2,3,4] [2,3,4,5]
リストの fmap は map なので、以下のように fmap を使えます。
> fmap (+1) [1,2,3,4] [2,3,4,5]
Maybe、Parser、IO も Functor のインスタンスです。
> fmap (+1) (Just 1) Just 2
これ以降、この記事では fmap の別名である <$> を使うことにします。<$> は、Control.Applicative で定義されています。
> :m Control.Applicative > (+1) <$> [1,2,3,4] [2,3,4,5] > (+1) <$> Just 1 Just 2
<$> の型は、
(<$>) :: (a -> b) -> f a -> f b
でした。-> は右結合なので、以下のように括弧を補えます。
(<$>) :: (a -> b) -> (f a -> f b)
こうすると、第一引数の関数をコンテナ対応に変更していることがはっきりします。
Functor、Applicative、Monad のコンテナは、「文脈」と呼ばれることもあります。あなたが、Monad をはっきり会得した思えるのは、きっと「Monad は文脈なんだ」ということを理解したときです。
文脈という言葉を使って <$> を説明すると、<$> は第一引数の関数を文脈に「もちあげる」ための関数です。たとえば、
> (+1) <$> Just 1
の (+1) <$> は、(+1) という文脈非依存の関数を Maybe という文脈に持ち上げているのです。なお、Maybe は「失敗するかもしれない」という文脈を表しますので、「失敗しない関数を失敗するかもしれない関数に変更している」と考えてもよいでしょう。
Functor に欠けているのは、コンテナ同士をくっ付ける機能です。小さな計算を組み合わせて、大きな計算を作れないのです。それを実現するのが Applicative です。
Applicative とは何ですか？
Applicative とは、pure と <*> というメソッドを提供する型クラスです。Applicative の親クラスは、Functor です。
class Functor f => Applicative f where pure :: a -> f a (<*>) :: f (a -> b) -> f a -> f b
おおざっぱに言えば、pure は return の別名です。つまり、新しいコンテナを作る関数です。<*> は、コンテナの中にある関数を、コンテナの中で関数適用するための関数です。<*> の型から、f という文脈を取り除いて下さい。関数適用、すなわち $ と同じ型になることが分かりますね。
($) :: (a -> b) -> a -> b
Applicative の <*> は、Functor の <$> と共に、Applicative スタイルを形成します。Applicative スタイルとは、以下のような書式です。
func <$> arg1 <*> arg2 <*> ....
<$> と <*> を頭の中で消せば、func arg1 arg2 ... となり、これは単なる関数適用です。Applicative スタイルとは、文脈の中での関数適用を簡便に書く書式であり、Applicative とはそれを実現するための型クラスです。
do のお話はまだしていませんが、同じことを do で書くと以下のようになります。
do a1 <- arg1 a2 <- arg2 ... return $ func a1 a2 ...
比べてみると、いかに Applicative スタイルが簡潔であるかが分かるでしょう。
Applicative スタイルは、よくパーサーと共に使われます。たとえば、各行にファイル名、オフセット、バイト数が書かれたファイルを解析することを考えましょう。以下のようなコードになります。(<* は、右の引数結果を捨てて、左の引数の結果を返す関数です。)
import Text.Parsec import Text.Parsec.String import Control.Applicative hiding (many,(<|>)) data FileInfo = FileInfo FilePath Integer Integer fileInfos :: Parser [FileInfo] fileInfos = many fileInfo fileInfo :: Parser FileInfo fileInfo = FileInfo <$> fileName <*> offset <*> size fileName :: Parser FilePath fileName = many1 (letter <|> digit) <* char ' ' offset :: Parser Integer offset = (read <$> many1 digit) <* char ' ' size :: Parser Integer size = (read <$> many1 digit) <* char '\n'
fileInfo を見れば、データ構成子 FileInfo が Parser の文脈の中で、次々に関数適用されていることが分かるでしょう。すなわち、小さな Parser を組み合わせて、大きな Parser を作っています。
このように、Applicative は逐次的にコンテナを連結できます。ただし、それぞれのコンテナは独立した計算を実行します。
Applicative にできないことは、前のコンテナの計算結果を用いて、後のコンテナが振る舞いを変えることです。別の言い方をすれば、前のコンテナの計算結果を、後のコンテナに渡す方法がありません。これを実現するのが Monad なのです。
では、再び Monad とは何ですか？
Haskell の Monad には残念ながら Applicative の制約がありませんが、すべての Monad は Applicative かつ Functor にすることができます。そして、Monad のインスタンスの多くは、Functor や Applicative のインスタンスとして定義されています。
そこで、ここでは以下のような理想化された世界を考えましょう。
class Functor m where (<$>) :: (a -> b) -> m a -> m b class Functor m => Applicative m where return :: a -> m a (<*>) :: m (a -> b) -> m a -> m b class Applicative m => Monad m where (>>=) :: m a -> (a -> m b) -> m b
pure と return は同一視できるので、ここではなじみ深い return を採用します。
この定義を見ると Monad の核心が、>>= だとはっきり分かりますね。第二引数の関数が、第一引数の計算結果を取ることに注目して下さい。
では、Applicative にできなくて、Monad にできるコードの一例を示しましょう。例としては、TLV (Type、Length、Value) パーサーが挙げられます。Value を解析するときは、直前の Length の結果を使わなくてはなりません。
具体的な実装は省略しますが、以下のようなコードになります。
data TLV = TLV Type Int Value tlv :: Parser TLV tlv = typ >>= \t -> len >>= \l -> val l >>= \v -> return (TLV t l v) typ :: Parser Type len :: Parser Int val :: Int -> Parser Value
理解すべきことは
- val は len の計算結果 l を受け取っている
- TLV t l v は文脈非依存の値なので、return で文脈に入れている
ことです。
Monad をまとめます。
- コンテナである
- コンテナを連結して大きなコンテナを作成できる
- 前のコンテナの結果に依存して、後のコンテナの振る舞いを変えられる
IO もコンテナなのですか？
そうです。
IO は命令書であり、命令ではありません。>>= を使えば、小さな命令書を合成して、大きな命令書を作成できます。最終的な命令書には main という名前が付きます。これを実行するのはランタイムです。
たとえば、getChar という関数を考えましょう。
getChar :: IO Char
命令型言語からやってきた人は、この関数を呼ぶと、文字が返ってくると思うでしょう。そして、呼び出した状況に応じて返ってくる文字は違うので、Haskell には副作用があると思うでしょう。
しかし、実際 getChar が返すのは「一文字読み込め」という命令書です。どんな状況においても、同じ命令書を返します。ですから、副作用はないのです。副作用を発生させるのは、命令書を実行するランタイムです。
ただ、IO が命令書であることを活かせるようになるには、相当修行を積む必要があります。そこで最初のうちは、「IO は副作用を起こす関数を表している」と理解しても問題はありません。IO が付いていなければ純粋で、IO が付いていれば副作用があって、それらを明確に区別できるから Haskell は素晴らしと理解しても結構です。
ただ、Haskell を使っていくどこかの時点で、正しい理解をして下さい。
Monad だと実行順序が指定できるのですか？
いいえ。それは Monad の機能ではありません。
Haskell では、プログラマーが記述した順序でプログラムが実行されるとは限りません。その具体的な例は遅延評価だけだと出力の順番が定まらない例を見て下さい。
ただ、プログラマーが記述した順序でプログラムが実行される場合があります。それはとても簡単な理屈で、前の結果に後が依存する場合、前を先に実行する必要があるからです。たとえば、以下のコードは記述順に実行されます。
isLetter x || isAscii x
それは、そうでしょう？ || は、以下のように定義されています。
(||) :: Bool -> Bool -> Bool True || _ = True False || y = y
トップレベルでのパターンマッチは、case の構文糖衣ですから、以下のように書き換えれます。
(||) :: Bool -> Bool -> Bool x || y = case x of True -> True False -> y
つまり、y を評価するか否かは、x に依存しています。さらに、x は Bool という正格データです。ですから、評価の順番が記述通りになるのです。
IO が記述順に実行されるのも、同じ理屈です。たとえば、IO の実現方法として、Worldという正格データ、すなわち実行環境を渡していく方法があります。
data IO a = IO (World -> (a,World)) instance Monad IO where (IO m) >>= f = IO $ \world -> case m world of (a, world') -> let IO m' = f a in m' world'
失敗系の Monad の実体が値そのものであるのに対し、状態系の Monad の実体は関数ですので、慣れないと少し難しいかもしれません。でも、記述順に実行される理屈は || と変わらないのです。
Monad が実行順を決めるのではなく、Monad のあるインスタンスの >>= が、実行順を守るように定義されているだけです。
do とは何ですか？
>>= の構文糖衣です。
先ほどの tlv を思い出しましょう
tlv = typ >>= \t -> len >>= \l -> val l >>= \v -> return (TLV t l v)
ちょっと気持ちが悪いのですが、折り返す場所を変えてみましょう。
tlv = typ >>= \t -> len >>= \l -> val l >>= \v -> return (TLV t l v)
ここで、<- という記号を導入すれば、各々の行をあたかも代入しているようなコードになることに気付いた人がいます。
tlv = do t <- typ l <- len v <- val l return (TLV t l v)
これが do の正体です。単なる >>= の構文糖衣に過ぎません。
Monad 則を教えて下さい。
以下が Monad 則です。
1: return x >>= f == f x 2: m >>= return == m 3: (m >>= f) >>= g == m >>= (\x -> f x >>= g)
Monad 則1 は return が左単位元だという意味ですが、プログラマーにはどうでもいい話です。これは、こういう書き換えが保証されているので、左の形は冗長だから、右のように書きましょうということです。do で表すと、さらに分かり易いかもしれません。
do y <- return x == do f x f y
左は冗長で、右は簡潔ですね。実は do f x も冗長で、f x で十分です。冗長なコードなんて書かないと思うかもしれませんが、コードを書き直すと知らないうちにこの形になっていることがあります。
Monad 則2 は return が右単位元だという意味ですが、プログラマーにはどうでもいい話です。これも、Monad 則1と同様に、書き換えが保証されているという意味です。こちらも do で書いてみましょう。
do x <- m == do m return x
左は冗長で、右は簡潔ですね。実は do m も冗長で、単に m で十分です。
Monad 則3 は、どういう順番でコンテナを合成しても意味は同じだということを表しています。つまり、m と f を合成してから g と合成しても、m を「f と g を合成したものに」合成しても、同じだと言っています。
左右が非対称なので、変数を補って対称性を持たせると、こうなります。
(m >>= \x -> f x) >>= \y -> g y == m >>= (\x -> f x >>= \y -> g y)
do で書くとこうなります。
do y <- do x <- m == do x <- m f x do y <- f x g y g y
右は結局、こういう意味です。
do x <- m y <- f x g y
つまり、書くなら最後のようにすっきり書きましょうということです。
よく分からない人は、do を命令型言語のブロック、つまり {...} に置き換えて下さい。どこを { } でくくろうと、意味は変わらないはずです。単にそれだけのことなんです。
なお、>>= は左結合ですので、単に
m >>= f >>= g
と書くと、
(m >>= f) >>= g
という意味になります。しかし、無名関数が以下のように混ざると、
m >>= \x -> f x >>= \y -> g y
以下のように解釈されます。
m >>= (\x -> f x >>= \y -> g y)
このおかげで、後ろの方で前の変数を参照できます。たとえば、こんな感じです。
m >>= \x -> f x >>= \y -> g (x,y)
実際に Monad を作ってみて下さい。
Maybe の実装例は見たことがあると思うので、ここでは Identity という Maybe よりも簡単な Monad を定義してみます。
data Identity a = Identity a deriving Show instance Monad Identity where return x = Identity x (Identity x) >>= f = f x
使ってみましょう。
> Identity 1 >>= \x -> return (x + 1) Identity 2
何の意味もないように思えるかもしれません。ここで重要なのは、Identity は文脈を表していることです。
繰り返しますが、Monad とは文脈です。同じ文脈同士のみを合成できます。Parser は Parser とのみ、IO は IO とのみ合成できます。そしてその結果は、それぞれ Parser と IO です。文脈は保持されるのです。
- [] (リスト)は、非決定性の文脈を表す
- Maybeは、失敗するかもしれないという計算の文脈を表す
- Parser は、パーサーという文脈を表す
- IO は、副作用を表現するという文脈を表す
Monad の文脈から逃れるには、文脈をちゃんと処理する必要があります。たとえば、Maybe から逃れるには、失敗を表す Nothing という場合を処理しないといけません。これで、処理忘れを防げるのです。
なお、IO という文脈から逃れる方法は、黒魔術を除いては、存在しません。
id が関数合成の初期値に使われるように、Identity は Monad トランスファーの基盤 Monad として使われます。
MonadPlus とは何ですか？
Monad の return と >>= は、それぞれ 1 と * に相当します。True と && に相当すると思っても結構です。
MonadPlus の mzero と mplus は、それぞれ 0 と + に相当します。False と || に相当すると思っても構いません。
つまり、Monad は連接を実現し、MonadPlus は選択を実現するのです。
>>=という共通のメソッドを持つ意味は何ですか？
共通のメソッドで実装しておけば、Monad の m の部分、すなわち文脈の指定を変えるだけで、コードの動作を変更できます。たとえば、同じ失敗系の Maybe とリストを考えましょう。これらの文脈は以下のように考えることもできます。
- Maybe - Nothing が失敗で、Just a が成功を表す。すなわち、答えが 0 個か 1 個の文脈を表す。
- リスト - [] が失敗で、それ以外が成功を表す。すなわち、答えが 0 個以上の文脈を表す。
では、二分木の探索問題を考えましょう。木は以下のような型を持ち、探索木ではないので要素は任意の順番で格納されているとします。
data Tree = Empty | Tree Int Tree Tree
この木を探索し、すべての答えを返すコードは、効率を無視すると以下のように書けます。
search :: (Int -> Bool) -> Tree -> [Int] search _ Empty = [] search p (Tree c l r) | p c = search p l ++ [c] ++ search p r | otherwise = search p l ++ search p r
使ってみましょう。
> search odd (Tree 3 (Tree 2 Empty Empty) (Tree 1 Empty Empty)) [3,1]
遅延評価ですので、先頭から順に結果を取り出すとバックトラックしているのと同じ効果を持ちます。非決定性の一般的な実装方法はバックトラックですから、遅延評価の下ではリストは非決定性の文脈を表すと言われるのです。
ここで、結果を一つだけ取り出すように変更したいと思ったとしましょう。抽象化されていなければ、型ごとにコードを書かないといけません。
実は、リストも Maybe も MonadPlus のインスタンスですから、以下のように抽象化して書き直すこともできます。
msearch :: MonadPlus m => (Int -> Bool) -> Tree -> m Int msearch _ Empty = mzero msearch p (Tree c l r) | p c = msearch p l `mplus` return c `mplus` msearch p r | otherwise = msearch p l `mplus` msearch p r
これだと、リストとして使うこともできますし、
> msearch odd (Tree 3 (Tree 2 Empty Empty) (Tree 1 Empty Empty)) :: [Int] [3,1]
Maybe として使うこともできます。
> msearch odd (Tree 3 (Tree 2 Empty Empty) (Tree 1 Empty Empty)) :: Maybe Int Just 3
多くの Parser は、Monad として実装されていますから、使い勝手は一緒です。たとえば、Parsec を習得しているなら、attoparsec を使うのは容易です。
Monad に慣れれば、Monad が自然となり、Monad にできるのにしてないデータ構造は、逆に不自然に思えるようになります。