第4回　「取り出し可能な値」のみを持つListモナド

　次に，Listモナドにおける>>=がちゃんと計算を合成するものになっているかどうかを考えてみましょう。

Prelude> [3,1,4] >>= \x -> [x, x*2, x*3]
[3,6,9,1,2,3,4,8,12]
Prelude> [3,1,4] >>= \x -> [x, x*2, x*3] >>= \x -> [x, x+1]
[3,4,6,7,9,10,1,2,2,3,3,4,4,5,8,9,12,13]
Prelude> [3,1,4] >>= \x -> [x, x*2, x*3] >>= return .id
[3,6,9,1,2,3,4,8,12]
Prelude> [3,1,4] >>= return . id >>= \x -> [x, x+1]
[3,4,1,2,4,5]

　上の例では，>>=はリストの先頭の値から順に関数を適用した結果のリストをつなぎ合わせて返しています。答えの数が乗法（multiplication）的に増えていくのがわかると思います。

　関数を適用するのが空リストであれば，答えも当然空リストになります。

Prelude> [] >>= \x -> [x, x*2, x*3]
[]
Prelude> [3,1,4] >>= \x -> if x < 5 then [] else return x
[]
Prelude> [3,1,4] >>= \x -> if x < 5 then [] else return x >>= \x -> [x, x+1]
[]
Prelude> [3,1,4] >> fail "error occur" >>= \x -> [x, x+1]
[]

　ここで，>>=の定義の中で使われているconcatは，空リストに対する計算をキャンセルする役割を果たしています。前に見た通り，concatはリストを連結する際に空リストを消してくれるので，以降余計な計算が行われることはありません。concatを使わない場合と使う場合の違いを以下に示します。

Prelude> map (\x -> if x < 2 then [] else return x) [3,1,4]
[[3],[],[4]]
Prelude> concatMap (\x -> if x < 2 then [] else return x) [3,1,4]
[3,4]

　さて，ここまでの説明で，if文の記述がうっとうしいと思った方がいるかもしれません。こうした人のために，Control.Monad（またはMonad）モジュールには糖衣構文としてguard関数が用意されています（参考リンク）。これを使えば，if文を使った式は以下のように書けます。

Prelude> :m Control.Monad
Prelude Control.Monad> [3,1,4] >>= (\x -> guard (x > 5) >> [x, x+1])
[]
Prelude Control.Monad> [3,1,4] >>= (\x -> guard (x > 2) >> [x, x+1])
[3,4,4,5]
Prelude Control.Monad> do {x <- [3,1,4]; guard (x > 2); [x, x+1]}
[3,4,4,5]

　guard関数が返すのはあくまでプレースホルダ（place-holder）であって，値そのものではないことに注意してください。試しにguard関数で計算を終了させると，その答えは以下のようになります（1行目最後の:: [[()]]は，型のあいまい性を排除するために必要な記述です）。

Prelude Control.Monad> map (\x -> guard (x > 2)) [3,1,4] :: [[()]]
[[()],[],[()]]
Prelude Control.Monad> [3,1,4] >>= \x -> guard (x > 2)
[(),()]

　()はユニット（unit）型であり，関数が有用な答えを返さない場合のプレースホルダとして使われるものです。前々回，repeatedとfinallyを使って文字を表示させる際に，とりあえず関数を実行させるためにreturn ()という値を与えたことを覚えているでしょうか？ あのときのように「関数が返す値そのものは必要ないが，次の関数に値が与えられたという事実が必要な」場合，その事実を示すためのタグとして()を使います。

　guard関数の定義は以下の通りです。

guard            :: MonadPlus m => Bool -> m ()
guard p          =  if p then return () else mzero

　「Listだけでなく他の型でも使えるように，MonadPlusという型構成子クラスに対して定義されていること」「その答えはmzeroであること」がわかると思います。MonadPlusクラスについても見ていきましょう。

Prelude Control.Monad> :i MonadPlus
class Monad m => MonadPlus (m::* -> *) where
  mzero :: m a
  mplus :: m a -> m a -> m a
        -- Imported from Control.Monad
instance MonadPlus []   -- Imported from Control.Monad
instance MonadPlus Maybe        -- Imported from Control.Monad

　MonadPlusクラスには，mzeroとmplusというメソッドが用意されています。これはそれぞれ，モナドにおけるゼロと加法（addtion）を定義するためのものです。これまで見てきた例からわかるように，モナドの>>=は乗法の意味を持っています。

　ここで，ゼロ（Listの場合は空リスト）が表れたらどうなるでしょうか？ Listモナドの場合にはconcatがうまく片付けてくれていましたが，そのような仕組みがない場合は，ゼロという値を>>=から>>=へと渡していくという無駄が起こる可能性があります（実際にはコンパイラの最適化によって取り除かれるかもしれませんが）。また，値がゼロの場合に備えて他の計算も行うようにしたいときには，その意図をソースコード上に示すためのものがあると便利です。こうした役割を持つのがMonadPlusです。

　もう察しがついているかもしれませんが，List型のMonadPlusクラスのインスタンスは「Haskell 98 言語とライブラリ 改訂レポート」では以下のように定義されています（参考リンク）。

instance  MonadPlus []  where
    mzero =  []
    mplus = (++)

　また，MonadPlusクラスのインスタンスは以下の四つの法則を満たすように定義しなければなりません。

1. mzero >>= f == mzero
2. m >>= (\x -> mzero) == mzero
3. mzero `mplus` m == m
4. m `mplus` mzero == m

　さて，上で見たguard関数を使用したコードをもう一度見てみましょう。

Prelude> :m Control.Monad
Prelude Control.Monad> [3,1,4] >>= (\x -> guard (x > 5) >> [x, x+1])
[]
Prelude Control.Monad> [3,1,4] >>= (\x -> guard (x > 2) >> [x, x+1])
[3,4,4,5]
Prelude Control.Monad> do {x <- [3,1,4]; guard (x > 2); [x, x+1]}
[3,4,4,5]

　これらはリストの内包表記によく似ています。

Prelude Control.Monad> [[x, x+1] | x <- [3,1,4], x > 5]
[]
Prelude Control.Monad> [[x, x+1] | x <- [3,1,4], x > 2]
[[3,4],[4,5]]
Prelude Control.Monad> [y | x <- [3,1,4], x > 2, y <- [x, x+1]]
[3,4,4,5]

　このため，リストの内包表記をListモナドの糖衣構文とみなすこともできます。ただし，現在の標準Haskellの定義では実際にはそのようにはなっていないので注意してください（実は，現在の標準Haskellの前身に当たるHaskell 1.4では，実際にこのように定義されていました（参考リンク））。

　リストの内包表記の簡潔さは魅力的ですが，複雑な計算を定義すると読みにくくなってしまいます。こうした場合には，Listモナドを使って書いたほうがよいでしょう。また，Listモナドを使えば，「非決定性計算（non-deterministic computation）」を行っていることを明確に表現することもできます。

　非決定性計算とは何でしょうか？ ある問題を解く際に効率の良いアルゴリズムがわかっている場合には，そのアルゴリズムを使って問題を解くことができます。一方，自然言語の構文解析などのように答えが自明ではない場合や十分に効率的なアルゴリズムが存在しない場合には，多少効率が悪くても正解に近そうな答えをヒューリスティック（heuristic，発見的）に推測していく必要があります。当然ながら，プログラムが次に行う動作は一意に定まりません。そこで,次に行う動作が一意に定まっている場合，すなわち「決定性（deterministic）」に対比する形で，非決定性と呼ぶのです。

　すでに見てきたように，Listモナドは，答えとなりうる複数の値や，計算で失敗が起こった場合といったものを扱うことができます。つまり，Listモナドを使うことで，総当り探索（exhaustive search）を用いた非決定性計算をシミュレートできるようになります。失敗が起こった場合に以後の計算がconcatによってキャンセルされるという動作は，ちょうどバックトラッキング（backtracking，バックトラック）を行ったのと同じことになります。

　このようなことを書くと，Listモナドは難しい問題やパズルを解くようなときにしか使えないと考える方がいるかもしれません。そこで，簡単かつ日常的に有用な非決定性計算の例として，4人のスケジュールを合わせるプログラムを考えてみましょう。日本語のコメントが存在するため，このプログラムをGHCを使って試す際には使用する文字コードに注意してください。GHC6.6の場合にはUTF-8N（BOMなしのUTF-8），それ以前のバージョンではEUC-JPにする必要があります。

import Control.Monad

schedule = do
    let d1 = 30 -- 最初の月の日数
        d2 = 31 -- 次の月の日数
        w1 = 4  -- 最初の土曜の日付
    w' <- [w1, w1+7 .. (d1 + d2)] -- 2カ月分の土曜のリスト
    w  <- (\x -> [x, x+1]) w' -- 2カ月分の土日のリスト

    -- 最初の月の17日までか，次の月
    guard $ not $ (\x -> 18 <= x  && x < d1) w
    -- 最初の月の4日ではない
    guard (w /= 4)
    -- 最初の月か，次の月の10日，24日，31日のいずれか
    guard $ w < d1 || w == 10 + d1 || w == 24 + d1 || w == 31 + d1

    dates <- return $ (\x -> if x < d1 then x else x - d1) w

    -- 31日でも11日でもない
    guard $ dates /= 31 && dates /= 11

    return dates

　まず$演算子について説明しておきましょう。$はカッコの役割を果たすものです。$よりも右側の値をカッコに包みます。つまり，

guard $ not $ (\x -> 18 <= x  && x < d1) w

の式は，以下の式と同じ意味です。

guard (not ((\x -> 18 <= x  && x < d1) w))

　$演算子は，do記法と同じくプログラムをカッコの羅列から解放して読みやすくする糖衣構文の役割を果たします。

　guard関数を使っている四つの式は，各々のメンバーが示した都合に当たります。&&演算子と||演算子およびnot関数は，それぞれ論理式のandとor，notです。このプログラムでは，それぞれの式を{}でくくって;で明示的に分ける代わりに，インデントを使ってレイアウトを揃えることで，それぞれの式の終了を暗黙的に記述しています（参考リンク）。

　w'という変数を束縛している[w1, w1+7 .. (d1 + d2)]という式は，エラトステネスのふるいの例で見たように，数列を生成するものです。w1+7の部分は，数値を列挙する際のやり方を示したものです。つまり，数値を列挙する際に，数値を7ずつ増やしていくことを意味しています。(d1 + d2)の部分は終端です。このリストが(d1 + d2)以下の数字を列挙していくことを示しています。

　guard関数を使った式の間にある「dates <- return $ (\x -> if x < d1 then x else x - d1) w」という式は，2カ月目の日付をカレンダー上の日付に戻すものです。

　つまり，scheduleという関数は，まず予定となる日付を列挙（生成）し，次に論理式で「都合の良い日（True）と悪い日（False）」すなわち「探索が成功する場合と失敗する場合」を挙げています。これにより，スケジュールを決定しているのです。答えは以下のようになります。

*Main> schedule
[5,12,10,24]

　最初の月の5日と12日，次の月の10日と24日が，4人の都合のよい日であることがわかります。

今回のまとめ

　今回は「取り出し可能な値」のみを持つコンテナの例として，Listモナドを紹介しました。

　Listモナドは「モナドにできそうだからしただけの単なる人工的な例（toy example）」などではなく，非決定性計算という計算を表現したものであることがわかっていただけたと思います。非決定性計算といっても何も難しいものではなく，スケジュール管理などの身近な用途に使えるものであることもわかってもらえたでしょうか？

　今回示した例では，わかりやすいように単に日付だけを扱いましたが，時刻などの制約を考慮するように拡張することも当然できます。また，GHC6.6で追加されたtimeパッケージのData.TimeモジュールにあるgregorianMonthLength関数を使えば，今回のように月の日数をいちいち指定しなくても，年と月を与えるだけで月の日数を取得できます。System.Timeモジュールを使えば，現在の日付を取得することも可能です。今回掲載したプログラムをいろいろと改造してみるとよいでしょう。

　モナドを学ぶにあたって一番重要なのは慣れです。何度も繰り返すうちに，自分のものにすることができるでしょう。HugsとGHCiで出てくるエラー・メッセージを見比べてみてもいいかもしれません。エラー・メッセージの中には，「Probable fix:」（GHCiの場合）といったようにプログラムの直し方のヒントが示されていることもあります。ただし，あくまで考えるのは自分です。エラーが出た場合，どこで勘違いしたのかをじっくり考えてみることも重要です。

*Main> :i Enum
class Enum a where
  succ :: a -> a
  pred :: a -> a
  toEnum :: Int -> a
  fromEnum :: a -> Int
  enumFrom :: a -> [a]
  enumFromThen :: a -> a -> [a]
  enumFromTo :: a -> a -> [a]
  enumFromThenTo :: a -> a -> a -> [a]
        -- Defined in GHC.Enum
instance Enum Float -- Defined in GHC.Float
instance Enum Double -- Defined in GHC.Float
instance Enum Bool -- Defined in GHC.Enum
instance Enum Ordering -- Defined in GHC.Enum
instance Enum Char -- Defined in GHC.Enum
instance Enum () -- Defined in GHC.Enum
instance Enum Int -- Defined in GHC.Enum
instance Enum Integer -- Defined in GHC.Num

*Main> ['a'..'z']
"abcdefghijklmnopqrstuvwxyz"
*Main> ['a','d'..'z']
"adgjmpsvy"
*Main> [False ..]
[False,True]

*Main> maxBound::Int
2147483647
*Main> maxBound::Bool
True
*Main> maxBound::Char
'\1114111'
*Main> maxBound::Integer

<interactive>:1:0:
    No instance for (Bounded Integer)
      arising from use of `maxBound' at <interactive>:1:0-7
    Possible fix: add an instance declaration for (Bounded Integer)
    In the expression: maxBound
    In the expression: maxBound :: Integer
    In the definition of `it': it = maxBound :: Integer