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

Just $ A sandbox

プログラミングと計算機科学とかわいさ

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という右随伴をもちます。すなわち、 F:\mathscr{C} \to \mathscr{D}とすると
 \mathscr{C}(Fc,d) \simeq \mathscr{D}(c,Ud) という集合としての同型があって、かつc,dのどちらについてもnaturalです*3

さらにFree Functorというのは`Free'、すなわち特にこれと言って条件を必要とせずに「自由な構造」を作り出します。自由な構造というのは、ここではモナドの圏になる(各対象がモナド、射がモナド準同型なる圏)という構造です。

Free Functorとは与えられたFunctorの圏からMonadの圏への自由函手というのは上のような意味です。Freeが本質的なのはその存在が函手圏の構造には依存しないところで、つまりMonadの中でも最も一般的なもの、あるいは最も小さい構造を持ったもの、という意味でぜひ理解して欲しい一例だったということでした。

*1:上の記事が分かる方は読む必要はありません、多分。

*2:また、Free MonadはFunctorから無条件で、つまり自由にMonadを得られるのでFreeという名前がついています。より強力にただのデータ型からMonadを作るOperational Monadというものについてもブログで扱いました。 cf. http://myuon-myon.hatenablog.com/entry/2013/06/09/135407

*3:ここでのFはFunctor圏からMonad圏への自由函手、UはMonad圏からFunctor圏への(モナドとしての構造を忘れるような)忘却函手です