人気ブログランキング | 話題のタグを見る

Yet Another Haskell Tutorial 32

9.6 Monad Plus

モナドのアクションを結合させる方は bind 演算子 (>>=) 以外に mplus 演算子がある。どちらも2つのアクションを結合して新しいアクションを生成する方法なので混同しやすいが、>>= 演算子の型は、

Prelude> :t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b

で、malus 演算子の場合は、

Prelude> :m Control.Monad
Prelude Control.Monad> :t mplus
mplus :: MonadPlus m => m a -> m a -> m a

なので、第2引数が >>= では (a -> m b) 型の関数であり、mplus では m a 型のアクションであるところが違っている。もちろん、意味も違う。

mplus を使うためには、目的のデータ型が MonadPlus (タイプ)クラスのインスタンスである必要がある。MonadPlus (タイプ)クラスの多相関数は2つあり、mzero と mplus だ。

Prelude Control.Monad> :info MonadPlus
class Monad m => MonadPlus m where
mzero :: m a
mplus :: m a -> m a -> m a
-- Defined in `Control.Monad'
instance MonadPlus [] -- Defined in `Control.Monad'
instance MonadPlus Maybe -- Defined in `Control.Monad'

数学的には、アクション m a と mzero と mplus の3つ組はモノイドをなしている。リスト型と Maybe 型は既に MonadPlus (タイプ)クラスのインスタンスだ。

こういう小難しい説明がなくても mplus の威力は例題プログラムを実行すると知ることができる。以下は、YAHT の例題プログラムを追っかけていく。

YAHT では、先ず Maybe 型と List 型における mzero と mplus の実装が紹介してある。

最初に Maybe 型について見てみる。

instance MonadPlus Maybe where
  mzero = Nothing
  mplus Nothing y = y
  mplus x _ = x

この動作を ghci で確認すると次のようになる。

Prelude Control.Monad> mzero :: Maybe Int
Nothing
Prelude Control.Monad> Nothing `mplus` Just 1
Just 1
Prelude Control.Monad> Just 1 `mplus` Just 2
Just 1
Prelude Control.Monad> Just 1 `mplus` Nothing
Just 1

Maybe 型のアクション Maybe a は大抵は検索値なので、Maybe a `mplus` Maybe a は最初の検索がヒットした場合はその値を戻し、最初の検索がヒットしなかった場合は二番目の検索の結果を戻すという意味になる事が多い。

次にリスト型について見てみる。

instance MonadPlus [] where
  mzero = []
  mplus x y = x ++ y

リスト型の mplus の意味は、単にリストの連結だ。

Prelude Control.Monad> mzero :: [Int]
[]
Prelude Control.Monad> [1,2] `mplus` [3,4,5]
[1,2,3,4,5]

これだけでは、ありがたみがあまり感じられないが、YAHT では前セクションで例示した searchAll 関数を改造して、グラフの経路検索に mplus を使う事で経路を全て検索できるように searchAll2 関数を作ってみせている。ghci で実験できるように次のプログラムをファイル searchAll2.hs に作成した。

import Control.Monad

data Graph v e = Graph [(Int, v)] [(Int,Int,e)]
  deriving Show

searchAll2 g@(Graph vl el) src dst
  | src == dst = return [src]
  | otherwise = search' el
  where
    search' [] = fail "no path"
    search' ((u,v,_):es)
      | src == u =
          (searchAll2 g v dst >>= \path ->
           return (u:path)) `mplus`
          search' es
      | otherwise = search' es

gr = Graph [(0,'a'),(1,'b'),(2,'c'),(3,'d')]
           [(0,1,'l'),(0,2,'m'),(1,3,'n'),(2,3,'m')]

gr2 = Graph [(0,'a'),(1,'b'),(2,'c'),(3,'d')]
            [(0,1,'l'),(0,2,'m'),(2,3,'m')]

searchAll 関数と searchAll2 関数の違いは search' 関数の定義に `mplus` search' es が付け加えられているところだけだ。

ghci で検証してみた。

Prelude> :l searchAll2.hs
[1 of 1] Compiling Main ( searchAll2.hs, interpreted )
Ok, modules loaded: Main.
*Main> searchAll2 gr 0 3 :: [[Int]]
[[0,1,3],[0,2,3]]
*Main> searchAll2 gr2 0 3 :: [[Int]]
[[0,2,3]]

セクション 9.4 の searchAll 関数では1つの経路の検索しかできなかったが、searchAll2 関数では全ての経路の検索ができる。また searchAll 関数で検索できなかったグラフ gr2 の経路も検索できるようになった。

searchAll2 関数は Maybe モナドでも使えるが、Maybe モナドの mplus 関数にはリストを連結する意味がないので、最初に検索が成功した経路のみが返される。しかし、searchAll の時と違って gr2 のグラフの経路検索にも成功する。

*Main> searchAll2 gr 0 3 :: Maybe [Int]
Just [0,1,3]
*Main> searchAll2 gr2 0 3 :: Maybe [Int]
Just [0,2,3]

例題のプログラムを実行して、mplus では何かすごい事をやっているのだなと実感する事ができる。しかし、それを理論的に理解しようとすると数学的な基礎が必要になってくるだろう。とにかく、例題のプログラムを参考にいろいろと使っているうちに、操作的に理解できればプログラムは作る事ができるし、mplus のパワーを利用できる。

Yet Another Haskell Tutorial 33 へ続く
by tnomura9 | 2013-03-17 09:11 | Haskell | Comments(0)
<< Yet Another Has... Yet Another Has... >>