HaskellのMonadは何をしているか
はじめに:モナドが何かわからないけど分かりたい人へ
この記事はあなたの為に書かれたものです! 「モナドって難しいそうだしよく分からない、けどきっと賢い人たちが『モナドとは何か』について素敵な説明を与えてくれるはず!」 …そういう期待を持っているまさにあなたのその勘違いを是正するためにこの記事はあります。
「モナドが何か」を理解するのはまずは諦めて下さい。
この記事は、世界一わかりやすいモナドの記事 - みょんさんの。を理解したいと思わない人のために、プログラミングの文脈でモナドに関する少しの考え方を提供するものだと考えて下さい*1。
what it is から how it works へ
モナドはモノではありません。だから「何」という質問に答えるのは難しいでしょう。数学的な公理を読者に投げつけることも意味不明な喩えでごまかすこともしたくはないので、少しだけ違う説明をします。
例を挙げましょう。
class Eq a where (==), (/=) :: a -> a -> Bool x /= y = not (x == y) x == y = not (x /= y)
さてこれはPreludeにあるEq型クラスの定義です。Eqは函数(==)の実装のみを与えればそれだけでインスタンスにすることができます。
私達が普段やるように、自分で定義したデータ型の同値性を定義してみましょう。
data Hoge = Fuga | Piyo instance Eq Hoge where Fuga == Fuga = True Fuga == Piyo = False Piyo == Fuga = False Piyo == Piyo = True -- Fuga /= Piyo -- = not (Fuga == Piyo) <- Eqにおける(/=)の定義より -- = not (False) <- instance Eq Hogeの定義より -- = True
しかしこれは以下にように書いても全く問題ありません。
data Hoge = Fuga | Piyo instance Eq Hoge where Fuga == Fuga = False -- <- ??? Fuga == Piyo = True -- <- ??? Piyo == Fuga = False Piyo == Piyo = True
インスタンス宣言の上2行は、明らかに私達が知っているような同値性とは異なります。しかしこれは全く正しいのです。
なぜなら、「Eqとは何が正しいのかを知っているのではなくて、何を正しいとみなしてプログラムを動かすか」を定義するからです。
Eqとは同値性を与える型クラスである、というのは誤解を招く表現です。上のように私達の知っている同値性とは異なるものがEqのインスタンスになる場合があるからです。以下では「Eqとは何を同値とみなすか」を与える型クラスであると考えて下さい。
この、what it isではなくてhow it worksという考え方は型クラスについて理解するのに便利なことが多々あります。
how Functor works
Eq型クラスは何を同値とみなすかを与えるような型クラスでした。ではFunctorとは何でしょうか?
Functorは、「どうやって函数を適用するか」を与えるような型クラスだと思って下さい。例を見ましょう。
class Functor f where fmap :: (a -> b) -> f a -> f b -- 「どうやって函数を適用するか」をfmapの実装で与える data Identity a = Identity a -- Identityの定義(実際は何もしない) instance Functor Identity where fmap f (Identity a) = Identity (f a) -- Identity aに対してはaにそのまま函数fを適用させる -- fmap (2+) (Identity 3) == Identity (2+3) data Maybe a = Nothing | Just a -- Maybeの定義 instance Functor Maybe where fmap _ Nothing = Nothing -- Nothingに対してはNothing fmap f (Just a) = Just (f a) -- Just aに対してはaにfをそのまま適用させる data List a = Cons a (List a) | Nil -- Listの定義(Listを[]に読み替えて下さい) instance Functor [] where fmap = map -- Listに対しては、mapという高階函数を使って函数を適用する instance Functor ((,) a) where fmap f (x,y) = (x, f y) -- 今aを固定したとき、(a,b)に対してはbに対してfを適用させる -- fmap (2+) (4,5) == (4, 2+5)
Functorというのは函数を適用させる方法を与えるような型クラスです。これは函数を適用して計算をさせるときに、どうやって函数の適用という操作をするかを定義しているのです。
実は、Monadも全く同じ事です。
how Monad works
Monadは、「どうやって計算に変換・計算を連結するかを与えるような型クラス」だと思ってみましょう。
class Monad m where return :: a -> m a -- ただの値aを(m a)という「計算(の結果)に」変換する (>>=) :: forall a b. m a -> (a -> m b) -> m b -- Aという計算結果とBという計算(をする函数)の合成をA >>= Bで与える instance Monad Identity where return a = Identity a -- ただの値aを(Identity a)という計算の結果に変換 (Identity a) >>= f = f a -- Identity aという計算の結果と計算fを合成(そのまま適用させるだけ) instance Monad Maybe where return a = Just a -- ただの値aを(Just a)という計算の結果に変換 (Just x) >>= k = k x -- Just xという結果(この場合は計算が「成功した」・「意味を持っている」)とkの計算をそのまま適用させて合成 Nothing >>= _ = Nothing -- Nothingという結果は何を合成してもNothing -- Just 9 >>= (\x -> Just (2+x)) == Just (2+9) -- Nothing >>= (\x -> Just (2+x)) == Nothing instance Monad [] where return x = [x] -- ただの値を[x]という計算の結果に変換 m >>= k = foldr ((++) . k) [] m -- リストの全要素を函数に適用させたものを結合し、それを計算の結果とする -- [1,2,3] >>= (\x -> [x+7, x+9]) == [1+7, 1+9] ++ [2+7, 2+9] ++ [3+7, 3+9] == [1+7, 1+9, 2+7, 2+9, 3+7, 3+9]
有名な例をいくつか挙げてみました。どれも、少し手を動かしてみると「どうやって計算に変換・計算を連結するかを与えている」ことが分かると思います。
さて、実はMonadで出てきた「計算」というのは何も数の計算には限りません。そもそも、「プログラム自体」計算の一種です。
-- Free Monad -- from http://hackage.haskell.org/packages/archive/free/3.4.2/doc/html/Control-Monad-Free.html#t:Free data Free f a = Pure a | Free (f (Free f a)) instance Functor f => Functor (Free f) where fmap f (Pure a) = Pure (f a) -- データ(Pure a)にはaにfを適用させてPure (f a)とする fmap f (Free fa) = Free (fmap (fmap f) fa) -- データ(Free fa)に対してはfをfmap (fmap f)としてfaに適用させる(これは再帰的な構造になっているので注意して下さい。faは(f (Free f a))という部分からなります) instance Functor f => Monad (Free f) where return = Pure -- ただの値をPureで包んでFree型に変換する Pure a >>= f = f a -- Pure aとfの計算の合成はf a Free m >>= f = Free (fmap (>>= f) m) -- Free mとfの計算の合成はfmap (>>= f)をmに適用させることで得られる
これが実際にプログラムのように動くことはFree Monadを使ってみよう!(2) - みょんさんの。でも説明しました。プログラム自体を(当然Input/Outputも含めて、です!画面に``hello!"と表示することも計算の一部、あるいは結果と見ているのです!)計算と考えれば上のようなものも作れます*2。
あるいは、「副作用のある値」を計算の結果と考えましょう。つまり、例えばキーボードからの入力によって得られるような、プログラムの中からは知りえない値は、外の世界で計算された結果であると考えます。するとこのMonadは「外の世界からの値を扱う計算の合成を与える」ことになります。
newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #)) -- IO a:外の世界からの値 -- (a -> IO b):ただの値aを外の世界からの値IO bに変える「計算」 -- IO b:IO aと(a -> IO b)の計算の合成の結果 (>>=) :: IO a -> (a -> IO b) -> IO b
これはIOモナドと呼ばれ、このモナドのおかげでHaskellは副作用を扱うのがとても簡単です。常にIOはモナドとしてしか表れないので、普通の処理は普通に行い、IOが絡むところだけはモナドを処理するための函数を書いてやることで純粋な部分と純粋でない部分(IOが混ざってくる部分)を綺麗に分離することができるのです。
そういえばMonadとは何だったのか
Monadが何かという説明は一切なしにここまで説明してきました。Monadは実は無条件になんでもMonadにしてよいのではなくて、ある条件を満たさなければなりません。
この法則のことをMonad則といいます。
return a >>= k == k a m >>= return == m m >>= (\x -> k x >>= h) == (m >>= k) >>= h
上に登場したものは全て(Identity, Maybe, List, Free, IO)この条件を満たしています。
しかしこれはただのMonadが満たすべき規則であって、Monadそれ自体ではありません。Monadとは何だったかというと、「計算への変換と合成を与える型クラス」でした。上の条件を少し眺めてみて下さい。
-- Maybeの例 Just a >>= k == k a Just a >>= Just == Just a Nothing >>= Just == Nothing Just a >>= (\x -> k x >>= h) == k a >>= h == (Just a >>= k) >>= h Nothing >>= (\x -> k x >>= h) == Nothing == (Nothing >>= k) >>= h
もちろん成り立っていますね。これが「明らか」に見えたら相当Monadに慣れている証拠です!
そもそもMonadというのは全然特殊なものではありません。その証拠に、いたる所にMonadはあります。なにせ「Free Monad」は全てのFunctorを無条件でMonadにできるくらいですから!Functorは「函数をどうやって適用させるか」を決めているだけなので、データ型の数だけ無数にあります。それらが全てMonadとして機能するわけです。
実際のプログラムの中ではIOモナドやOperational Monadと行った「便利で」「革命的な」モナドがたくさん使われます。しかし根本的には全て「計算への変換と合成」を定義しているに過ぎません。そしてそれらは上の関係を満たしている、ということです。IOモナドは外の世界の値を計算の結果に、そしてOperational Monadは(構造としてはFree Monadの構造と同じです)プログラムそれ自体を計算の結果と見ているということです。
あなたの周りにはたくさんのMonadがあります。そしてそれらを簡単に作ったり扱うための函数がすでにたくさん揃っています。あとは使いこなすだけですね。
それではHappy Monad Life!
補足:Free Functor
Free Functor Fは左随伴で、Forgetful Functor Uという右随伴をもちます。すなわち、とすると
という集合としての同型があって、かつc,dのどちらについてもnaturalです*3。
さらにFree Functorというのは`Free'、すなわち特にこれと言って条件を必要とせずに「自由な構造」を作り出します。自由な構造というのは、ここではモナドの圏になる(各対象がモナド、射がモナド準同型なる圏)という構造です。
Free Functorとは与えられたFunctorの圏からMonadの圏への自由函手というのは上のような意味です。Freeが本質的なのはその存在が函手圏の構造には依存しないところで、つまりMonadの中でも最も一般的なもの、あるいは最も小さい構造を持ったもの、という意味でぜひ理解して欲しい一例だったということでした。
Yoneda lemmaとOperational Monad
最近Haskellerの間で人気になりつつある(?)Operational Monadというものについての記事です。
サンプルプログラム
Operational Monadは http://hackage.haskell.org/package/free-operational で定義されています。後でも説明しますがこれはFree Monadの構造をもったモナドになります。
以下のコードはhttps://gist.github.com/myuon/5737483に載せておきました。
{-# LANGUAGE GADTs #-} import Control.Monad import Control.Monad.Operational.Simple data Simple a where End :: Simple a Put :: String -> Simple () Get :: Int -> Simple String
ここではGADT拡張を使います。上ではSimpleというデータ型のコンストラクタの宣言を、型クラスの函数宣言のようにして作っています。
Free Monadの記事(Free Monadを使ってみよう! - みょんさんの。とFree Monadを使ってみよう!(2) - みょんさんの。)のところでもやりましたが、Free Monadとして使うために、必要な値を受け取ってSimple型を返す函数を作ってあげなければいけません。
それが以下です。
put :: String -> Program Simple () put = singleton . Put end :: Program Simple a end = singleton End get :: Int -> Program Simple String get = singleton . Get
最後に、これをrunするためのものが必要ですね。ここで使われているinterpretという函数はControl.Monad.Operational.Simpleで定義されています。
run :: Program Simple a -> IO a run = interpret step where step :: Simple x -> IO x step (Put a) = putStrLn a step End = putStrLn "End" >> undefined step (Get n) = replicateM n getChar
これでおしまいです。あとは適当なプログラムを書いて走らせましょう。
tinyProgram = do put "hello, world!" end main = run tinyProgram
実行結果
hello, world! End Operational.hs: Prelude.undefined
Operational Monad
上で作ったtinyProgramはdo記法を使っていることからも、Simple型がモナドとして機能していることは分かります。しかし、私達はSimple型をMonadはおろかFunctorにすらしていません。しかしなぜこんなことができるのでしょうか?結論から言ってしまえば、Simple型はOperatinal Monadの力によってFunctorを経てFree Monadの構造が与えられているのです。
どういうことでしょうか。Operational Monadの定義から考えてみましょう。
-- http://hackage.haskell.org/packages/archive/free-operational/0.3.0.0/doc/html/src/Control-Monad-Operational-Simple.html#Program newtype Program instr a = Program { toFree :: Free (Yoneda instr) a }
実は、重要なのはここだけです。FreeというのはFree Monadですが、その中にYonedaというものが見えると思います。これはつまり、
inst | ただのデータ型 |
Yoneda instr | Functor |
Free (Yoneda instr) a | Free Monad |
という関係になっているのです!
次に出てくる疑問は、ではただのデータ型をFunctorにしているYonedaというのは何?ということでしょう。これは圏論で登場する米田の補題という有名な補題に関係があります。
(Yoneda f) functor
米田の補題を理解するためには少しだけ準備が必要ですが、ここに書ききれるものではないので簡単に説明だけして終わることにします。
興味がある方は補足のところを読んで下さい。
米田の補題で重要なのは、普通の集合と函手の集合には全単射の関係があるということです。つまり、ある集合から1つ元を取り出すと、函手が1つ作れる、あるいはその逆も可能という対応関係です。
つまり、自分でデータ型を、函手に対応づけすることができる = データ型から函手を作ることができる という対応です。
以下に定義を示します。
-- http://hackage.haskell.org/packages/archive/kan-extensions/3.1.1/doc/html/src/Data-Functor-Yoneda-Contravariant.html#Yoneda data Yoneda f a where Yoneda :: (b -> a) -> f b -> Yoneda f a instance Functor (Yoneda f) where fmap f (Yoneda g v) = Yoneda (f . g) v
ご覧の通り、(Yoneda f)はFunctorになっていますね!これは、与えられたfというデータ型を使って、(Yoneda f)というFunctorを創りだすことができるということを示しています。まさに魔法のようですね!
何度も言いますが、与えられたデータ型を使って、(Yoneda f)というFunctorを創りだすことができることが「米田の補題」によって保障されているわけです。
(補足)Yoneda lemma
米田の補題は圏論では非常に有名な補題(というか定理)で、ここから色々な定理を示すことができる強力な定理です。
補題のステートメントは単純で、
が函手(functor)のとき、なる写像が存在する(つまり上の写像が全単射となる)ということです。
ここで、、つまりという自然変換をという元に対応させています。
上で出てきた函手を、Yoneda函手と言います。
これは函手圏の射である自然変換の集合と、集合圏の対象である集合との間に全単射の関係があるということを意味しています。
これによって、自然変換と集合の元を対応させることができます。これが、Haskellでは一体どういった意味を持つのでしょうか?
data Yoneda f a where Yoneda :: (b -> a) -> f b -> Yoneda f a instance Functor (Yoneda f) where fmap f (Yoneda g v) = Yoneda (f . g) v
Yonedaは射(b -> a)と対象(f b)を受け取ってYoneda f aなるデータ型を返します。f(に対して定義されたfmap)を上で出てきた函手Fだと思いましょう。
圏論 | Haskell |
---|---|
の射 | (b -> a) |
fmap :: (b -> a) -> f b -> f a | |
fmap :: (b -> a) -> (Yoneda f) b -> (Yoneda f) a | |
nat*1 :: forall*2 b. f b -> (Yoneda f) b | |
Yoneda (b -> a) :: f b -> (Yoneda f) a | |
Yoneda (b -> a) (f b) :: (Yoneda f) a |
米田の補題が言っているのは、(Yoneda f) a と nat :: forall b. f b -> (Yoneda f) b とが確かに対応すること、つまりこの意味でのYonedaが
data Yoneda f a where Yoneda :: (b -> a) -> f b -> Yoneda f a
と定義することができる(このような写像が常に存在する)ことを言っていたのです。
参考文献
- Freeモナドを超えた!?operationalモナドを使ってみよう - モナドとわたしとコモナド Operational Monadの存在をここで知りました
- http://hackage.haskell.org/package/free-operational YonedaとFree Monadを使ったOperational Monadの実装
- http://hackage.haskell.org/package/kan-extensions Yoneda等が定義されているパッケージ
- Understanding Yoneda | Bartosz Milewski's Programming Cafe 自然変換をHaskellで表現するとはどういうことか、などに興味があれば読んでみて下さい。補足のところで説明もなく使ったforallの扱いなどが丁寧に解説されています。