8. Monad

この文書では Monad について述べます。Monad は成功しないかも知れない計算を組み合わせる手法で、探索、IO、構文解析などに使われます。

Monad は実はそれほど難しい概念ではありません。 "Haskell は Monad を使って参照透明性をおかすことなく IO を実現している。" といううたい文句や、"Monad を理解するのは難しいかもしれない" などという脅しを気にしないで、Haskell 98 にある定義を見れば分かりやすいと思います。

上級 Haskeller は Monad を駆使して難しいことをやりますが、それは Monad が難しいのではなく、彼らのやっていることが難しいだけです。つまり、Monad を使うと難しいことが出来るが、Monad そのものが難しいわけではないということです。

1. Monad は class

Haskell 98 では Monad というのは class （つまり総称関数のセット）として定義されています。たまに、"List は Monad" というようなフレーズを見かけますが、正確には、"List は Monad の instance である。"、"List には Monad がある" または、 "Monad の instance が List ([a]) という data で定義されている" ということになります。従って、class Monad で定義されている総称関数は data 型によって違う動作をすることになります。show や (==) のような分かりやすい総称関数だと data 型によって違う動作をしても気になりませんが、見慣れない Monad の総称関数が data 型ごとに動作が違うと混乱するかもしれません。そのような時は落ち着いて、Haskell 98 を見てみるのが良いと思います。

それでは、class Monad の定義を見てみましょう。次のようになっています。

[code 1]

-- in predefined types and class
class  Monad m  where
    (>>=)   :: m a -> (a -> m b) -> m b
    (>>)    :: m a -> m b -> m b
    return  :: a -> m a
    fail    :: String -> m a

    m >> k  =  m >>= \_ -> k
    fail s  = error s

[code 1] から class Monad には 4 つの総称関数 (>>=), (>>), return, fail があることが分かります。また、 "class Monad m where" とか "m a" だとか "m b" といった記述があるので、これらの総称関数は Maybe, List, IO などの何か複合的 data 型に関するものだということ、さらに、raturn とか fail という単語がみえるので、失敗するかもしれない計算に関わっているということが分かります。

さらに、

    (>>=)   :: m a -> (a -> m b) -> m b

から、(>>=) は引数として、

複合型 data 'm a' と、
a から複合型 data 'm b' を作る関数

をとり、複合型 data m b を返す高階関数であることがわかります。

そして、(>>) は、

    m >> k  =  m >>= \_ -> k

から、m の値を捨てて、k を呼び出す関数であることが分かります。 (Lisp の progn に似ています。)

以上のことから、Monad というのは失敗するかもしれない計算をつなぎ合わせる総称関数群であることが分かります。

2. Maybe の Monad

これまでの話は抽象的過ぎて分かりにくいので、簡単な例を挙げて説明したいと思います。 Monad のうちで一番簡単なのは Maybe の Monad で、以下のように定義されています。

[code 2]

-- in standard-prelude
instance  Monad Maybe  where
    (Just x) >>= k   =  k x
    Nothing  >>= k   =  Nothing
    return           =  Just
    fail s           =  Nothing

つまり、以下のようになります。

Just x を次の計算 k に渡すと k x になる。（つまり、Just を剥ぎ取って次の計算に渡す。）
Nothing は次の計算へ行っても Nothing である。
return は Just である。
fail s は Nothing である。

例: 文字列を整数に変換

文字列を整数に変換することを考えましょう。まず、１文字ずつ読み込む関数 s2i を定義しましょう。 s2i は文字列から先頭の１文字を読み込んで、整数に変える関数です（[code 3] 10--13 行目）。 s2i は整数と文字列の tuple を引数に取り、[example 1] のような動作をします。

[example 1]

01:     EasyMonad> s2i (0,"12345")
02:     Just (1,"2345")
03:     EasyMonad> s2i (1, "2345")
04:     Just (12,"345")

[code 3]

01:     -- easy_monad.hs
02:     -- a small script for haskell8.html
03:     
04:     module EasyMonad where
05:     
06:     import Char
07:     
08:     --- Let's convert a String to Int if the String is [0-9]+
09:     -- s2i is a (reading one character) function
10:     s2i :: (Int, String) -> Maybe (Int, String)
11:     s2i (i, "") = Just (i, "")
12:     s2i (i, c:cs) | isDigit c = Just (i*10 + ord c - ord '0', cs)
13:                   | otherwise = Nothing
14:     
15:     -- same as s2i, written in Monadic term
16:     s2i' :: (Int, String) -> Maybe (Int, String)
17:     s2i' (i, "") = return (i, "")
18:     s2i' (i, c:cs) | isDigit c = return (i*10 + ord c - ord '0', cs)
19:                    | otherwise = fail "The char is not Digit"
20:     
21:     -- whole function to convert string to Maybe Int
22:     str2int :: String -> Maybe Int
23:     str2int "" = Nothing
24:     str2int str = iter (0, str)
25:      where iter (i, "") = Just i
26:            iter (i, cs) = let p = s2i (i, cs)
27:                           in if p == Nothing
28:                                  then Nothing
29:                                  else p >>= iter

このコードは付録の easy_monad.hs に入っているので、それを hugs などの対話的な処理系で load し、[example 2] のようにして遊んでみてください。文字列が読み込まれていく様子と(>>=) の使い方が分かると思います。

[example 2]

EasyMonad> s2i (0, "123")     -- read one
Just (1,"23")
EasyMonad> s2i (0, "123") >>= s2i             -- read two
Just (12,"3")
EasyMonad> s2i (0, "123") >>= s2i >>= s2i     -- read three
Just (123,"")
EasyMonad> s2i (0, "12a") >>= s2i >>= s2i     -- I cannot convert "12a" into an Int
Nothing
EasyMonad> s2i (0, "abc") >>= s2i >>= s2i     -- I cannot convert "abc" into an Int, either
Nothing

s2i' (code 1, 16--19 行目）は s2i を Monad 用語で書き換えたものです。全く同様に動作します。

str2int (code 1, 22--29 行目）は s2i を用いて String を Maybe Int に変換する関数です。

EasyMonad> str2int "12345"
Just 12345
EasyMonad> str2int "12+345"
Nothing

この例から Monad 自体はそんなに難しくないことがお解かりいただけたと思います。

3. Monad 則

計算をスムーズにつなげるために、Monad で定義される総称関数は３つの Monad 則を満たさなければなりません。既存の Monad は全てこの条件を満たしています。３番目の規則は、下に示す計算の結合則を保証するものです。

       c1 >>= c2 >>= c3
⇔     (c1 >>= c2) >>= c3
⇔     c1 >>= (c2 >>= c3)  (注 1)

注 1: 上のは概念的に書いたもの。Haskell のコードとして書くと c1 >>= (\x -> c2 x >>= c3) 。

自前の Monad を作るときは Monad 則を満たすようにして下さい。

[Monad 則]

return a >>= k = k a
m >>= return = m
m >>= (\x -> k x >>= h) = (m >>= k) >>= h

試しに Maybe の Monad が Monad 則を満たしていることを確認してみましょう。

-- Law 1
return x >>= k   ⇒   Just x  >>= k   ⇒    k x

-- Law 2
Just x >>= return    ⇒    return x      ⇒        Just x

-- Law 3
Just y >>= (\x -> k x >>= h)   
 ⇒       (\x -> k x >>= h) y                  
 ⇒        k y >>= h
 ⇒       (Just y >>= k) >>= h

4. IO の Monad

Haskell では、IO の結果として得られる値は、IO a という型を持ち、a とは区別されます。こうすると、IO の結果を、直接は、関数の引数にすることが出来ないので、本体の関数部分の参照透明性が保持されます。

IO の結果を関数に渡すため IO の Monad が定義されています。 '...' の部分は実装に依存します。

instance Monad IO where
   (>>=)  = ...
   return = ...
   fail s = ioError (userError s)

5. do 記法

do 記法は (>>=), (>>) を使った通常の記法の構文糖衣です。 do 記法を用いると手続き言語風になるので IO などを記述するときは分かりやすくなります。
以下に do 記法を通常の記法に翻訳する規則を示します。

翻訳前	翻訳後
do{foo}	foo
do{foo; bazs}	foo >> do{bazs}
do{let hoge; bazs}	let hoge in do{bazs}
do{ p <- foo; bazs}	let ok p = do{bazs} ; ok _ = fail "..." in foo >>= ok

４番目の翻訳規則は fail を考慮しているため一見すると分かりにくくなっていますが、基本的には以下の式と同等です。
[翻訳規則 4']

do{ p <- foo; bazs} ⇒ foo >>= (\ p -> do{bazs})

以下に通常の記法と do 記法を用いたエコープログラムを示します。

01:     -- simple echo
02:     -- do notation
03:     my_echo :: IO()
04:     my_echo = do putStrLn "Enter something."
05:                  str <- getLine
06:                  putStrLn $ "You have entered: " ++ str
07:     
08:     -- conventional notation
09:     my_echo' :: IO()
10:     my_echo' = putStrLn "Enter something." >>
11:                getLine >>= (\str -> putStrLn $ "You have entered: " ++ str)

6. List の Monad

List の Monad は以下のように定義されています。

instance  Monad []  where
    m >>= k          = concat (map k m)
    return x         = [x]
    fail s           = []

(>>=) が Maybe 型とだいぶ異なっています。 List における (>>=) は、リストの要素全てに k を作用させ、それを concat でつなぎ合わせるということです。また、return はリストを作ること、 fail は空リストです。

以下にリストの要素のうち奇数を選んでそれを c 倍する関数を

通常の書き方 (mul_odd1, 4--7 行目）
Monad 用語を使った書き方 (mul_odd2, 10--13 行目）
内包表現を使った書き方 (mul_odd3, 16--17 行目）

で書いてみました、これらの関数の比較から、内包表現は List の Monad の構文糖衣であることが分かります。

01:     --- Monad at List
02:     --- if odd then (*c) else fail
03:     --- list notation
04:     mul_odd1 :: Int -> [Int] -> [Int]
05:     mul_odd1 c xs = xs >>= (\x -> if odd x
06:                                       then [x*c]
07:                                       else [])
08:                                       
09:     --- monadic notation
10:     mul_odd2 :: Int -> [Int] -> [Int]
11:     mul_odd2 c xs = xs >>= (\x -> if odd x
12:                                       then return (x*c)
13:                                       else fail "I like odd.")
14:                                       
15:     ---  internal capsule
16:     mul_odd3 :: Int -> [Int] -> [Int]
17:     mul_odd3 c xs = [x*c | x <- xs, odd x]

EasyMonad> mul_odd2 10 [1,2,3,4,5]
[10,30,50]

7. mapM と mapM_

map と Monad を組み合わせると便利なことがあります。 mapM は map と (>>=) を、mapM_ は map と (>>) を組み合わせたものです。
mapM_ はリストの要素に１引数の関数 f を作用させ、値は返しません。一方、mapM はリストの要素に f を作用させ、全ての要素について return を返したら、返ってきた値のリストを返します。一方、１つでも fail があると全体も fail を返します。定義と、例を示します。

[定義]

sequence       :: Monad m => [m a] -> m [a] 
sequence       =  foldr mcons (return [])
                    where mcons p q = p >>= \x -> q >>= \y -> return (x:y)

sequence_      :: Monad m => [m a] -> m () 
sequence_      =  foldr (>>) (return ())

-- The xxxM functions take list arguments, but lift the function or
-- list element to a monad type

mapM             :: Monad m => (a -> m b) -> [a] -> m [b]
mapM f as        =  sequence (map f as)

mapM_            :: Monad m => (a -> m b) -> [a] -> m ()
mapM_ f as       =  sequence_ (map f as)

[例]

foo :: [Int] ->IO()
foo = mapM_ print
{-
foo [1,2,3] ⇒ sequence_ $ map print [1,2,3]
            ⇒ sequence_ [(print 1), (print 2), (print 3)]
            ⇒ print 1 >> print 2 >> print 3
-}

baz :: [Double] -> Maybe [Double]
baz xs = mapM  bar xs
 where bar x = if x > 0
                   then return (sqrt x)
                   else fail "I like positive."

{-
baz [1,4,9] ⇒ sequence [Just 1.0, Just 2.0, Just 3.0]
            ⇒ Just [1.0, 2.0, 3.0]

baz [1,-4,9] ⇒ sequence [Just 1.0, Nothing, Just 3.0]
            ⇒ Nothing
-}

8. 終わりに

Monad については All about Monad （日本語訳）に詳しく書いてあります。また、 haskell.org に Web 上の Monad の解説記事の一覧があります。