お気楽 Haskell プログラミング入門

はじめに

いよいよ今回から Haskell の最難関といわれている「モナド (Monad)」にチャレンジします。Haskell のモナドは Applicative を強化した型クラスです。今回はモナドの基本とリストモナドについて説明します。

●モナドとは？

Haskell のモナドは Applicative, Functor と同様に型クラスのひとつです。モナドの定義をコマンド :info で調べると、次のように表示されます。

ghci> :i Monad
type Monad :: (* -> *) -> Constraint
class Applicative m => Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  {-# MINIMAL (>>=) #-}
        -- Defined in ‘GHC.Base’
instance Monoid a => Monad ((,) a) -- Defined in ‘GHC.Base’
instance (Monoid a, Monoid b) => Monad ((,,) a b)
  -- Defined in ‘GHC.Base’
instance (Monoid a, Monoid b, Monoid c) => Monad ((,,,) a b c)
  -- Defined in ‘GHC.Base’
instance Monad ((->) r) -- Defined in ‘GHC.Base’
instance Monad IO -- Defined in ‘GHC.Base’
instance Monad [] -- Defined in ‘GHC.Base’
instance Monad Maybe -- Defined in ‘GHC.Base’
instance Monad Solo -- Defined in ‘GHC.Base’
instance Monad (Either e) -- Defined in ‘Data.Either’

ここで、関数 return と演算子 >>= に注目してください。この 2 つがモナドの主な機能です。m は型クラス制約で Applicative を指定されているので、Applicative と同様に型変数をひとつ取る型構築子になります。関数 return の型は a -> m a なので、任意のデータを m の中に格納して返す働きをします。

return は Applicative の関数 pure と同じですが、昔の Monad は Applicative を継承していなかった (もっと昔は Applicative が定義されていなかった) ので、return が用意されています。今のバージョンでは return のかわりに pure を使っても動作しますが、昔からの慣習に従ってモナドでは return を使うことにします。

簡単な例を示しましょう。

ghci> return 1 :: Maybe Int
Just 1
ghci> return 1 :: [Int]
[1]
ghci> return 1 :: Either a Int
Right 1

引数を 1 とすると、文脈が Maybe であれば Just 1 に、リストであれば [1] に、Either であれば Right 1 になります。なお、モナドはデータ型によって、Maybe モナド、リストモナド、Either モナドというように、データ型を付けて呼ばれています。

>>= の型はちょっと難しいですね。第 1 引数 (左辺値) は m a なので、モナドを受け取ることがわかります。第 2 引数 (右辺値) は関数ですが、計算結果をモナドに格納して返します。つまり、演算子 >>= は左辺値のモナドから値を取り出し、それを関数に渡して評価し、その返り値 (モナド) をそのまま返す、という働きをします。

簡単な実行例を示します。

ghci> Just 1 >>= \x -> return (x * 2)
Just 2
ghci> Nothing >>= \x -> return (x * 2)
Nothing
ghci> [1,2,3,4,5] >>= \x -> return (x * 2)
[2,4,6,8,10]
ghci> [] >>= \x -> return (x * 2)
[]
ghci> getLine >>= \x -> return (reverse x)
hello, world
"dlrow ,olleh"
ghci> Right 1 >>= \x -> return (x * 2)
Right 2
ghci> Left "error" >>= \x -> return (x * 2)
Left "error"

計算結果は return を使ってモナドに格納します。このとき、左辺のデータ型が Maybe であれば値は Just に格納され、リストであれば値はリストに、I/O アクションであれば IO に、Either であれば Right に格納されます。Nothing, 空リスト [ ], Left の場合は値がないので、それをそのまま返します。Functor や Applicative と同様にモナドでも文脈は保たれていることに注意してください。

●演算子 >>= で関数を連結する

演算子 >>= の返り値の型は m b なので、>>= を使って関数を連結していくことができます。このとき、モナドから取り出された値は右辺の関数の引数に渡されるので、>>= は「バインド (bind) 演算子」とか「束縛演算子」と呼ばれています。

簡単な例を示しましょう。

ghci> Just 1 >>= \x -> return (x*2) >>= \x -> return (x+10)
Just 12
ghci> Nothing >>= \x -> return (x*2) >>= \x -> return (x+10)
Nothing
ghci> [1,2,3,4,5] >>= \x -> return (x*2) >>= \x -> return (x+10)
[12,14,16,18,20]
ghci> [] >>= \x -> return (x*2) >>= \x -> return (x+10)
[]

最初の関数は引数 x を 2 倍し、次の関数は引数 x に 10 を加算します。2 つの関数を >>= でつなげると、 x * 2 + 10 を計算する処理になります。左辺の値が Nothing や空リストの場合、>>= はそれをそのまま返すので、返り値も Nothing や空リストになります。

もう一つ簡単な例を示しましょう。

ghci> Just 1 >>= \x -> Just 'a' >>= \y -> return (x, y)
Just (1,'a')
ghci> getLine >>= \x -> getLine >>= \y -> return (x++y)
hello,
world
"hello,world"

最初に例では、Just 1 の 1 がラムダ式の引数 x に渡され、次に Just 'a' の 'a' がラムダ式の引数 y に渡されます。そして、最後に return (x, y) で x と y をタプルに格納して返します。

次の例では、最初の getLine で文字列を読み取り、それをラムダ式の引数 x に渡します。そして、再度 getLine で文字列を読み取ってラムダ式の引数 y に渡し、その中で文字列を連結して返します。これで入力された 2 つの文字列を連結することができます。

リストモナドの場合、リスト内包表記と同じ動作になります。簡単な例を示します。

ghci> [(x, y)| x <- [1,2,3], y <- "abc"]
[(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c'),(3,'a'),(3,'b'),(3,'c')]
ghci> [1,2,3] >>= \x -> "abc" >>= \y -> return (x, y)
[(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c'),(3,'a'),(3,'b'),(3,'c')]

リスト内包表記はリストモナドの構文糖衣と考えることができます。

●自分でモナドを定義する

それではここでモナドの理解を深めるため、私たちでモナドを定義してみましょう。型クラスの名前は Mmonad とします。Mmonad の定義は次のようになります。

リスト : Mmonad の定義

class Mmonad m where
  ret  :: a -> m a
  bind :: m a -> (a -> m b) -> m b

return と演算子 >>= は Haskell の Prelude で使用されているので、ここでは ret と bind という名前にしました。ret の仕様は return と、bind の仕様は演算子 >>= と同じです。

次は Maybe、Either, IO, リスト を Mmonad のインスタンスに設定します。次のリストを見てください。

リスト : インスタンスの設定

-- Maybe
instance Mmonad Maybe where
  ret x = Just x
  Nothing `bind` _ = Nothing
  Just x `bind` f  = f x

-- Either
instance Mmonad (Either a) where
  ret x = Right x
  Left x `bind` _ = Left x
  Right x `bind` f = f x

-- IO
instance Mmonad IO where
  ret = return
  action `bind` f = do
    x <- action
    f x

-- リスト
instance Mmonad [] where
  ret x = [x]
  xs `bind` f = concatMap f xs

ret の定義は Applicative の pure と同じです。bind の定義も簡単ですね。Maybe は左辺が Nothing であれば Nothing を返します。そうでなければ、左辺 Just x から値 x を取り出して、右辺の関数 f に渡して評価します。Either, IO の場合も同じです。

リストの場合はちょっと複雑です。左辺の関数 f の返り値はリストに格納されているので、xs の要素に適用した結果を連結しないといけません。この処理は関数 concatMap を使うとうまくいきます。

それでは実際に試してみましょう。

ghci> Just 1 `bind` \x -> ret (x * 2)
Just 2
ghci> Nothing `bind` \x -> ret (x * 2)
Nothing
ghci> Right 1 `bind` \x -> ret (x * 2)
Right 2
ghci> Left "error" `bind` \x -> ret (x * 2)
Left "error"
ghci> getLine `bind` \x -> ret (reverse x)
hello, world
"dlrow ,olleh"
ghci> [1,2,3,4,5] `bind` \x -> ret (x * 2)
[2,4,6,8,10]
ghci> [1,2,3] `bind` \x -> "abc" `bind` \y -> ret (x,y)
[(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c'),(3,'a'),(3,'b'),(3,'c')]

●モナドと do 構文

モナドは演算子 >>= を使わずに do 構文で操作することができます。do 構文はモナドの構文糖衣と考えることができます。次の例を見てください。

ghci> getLine >>= \x -> getLine >>= \y -> return (x++y)
hello,
world
"hello,world"
ghci> do {x <- getLine; y <- getLine; return (x++y)}
hello,
world
"hello,world"

do 構文で実行される処理は演算子 >>= で連結されていると考えてください。getLine >>= \x -> ... は、do 構文の中では x <- getLine; ...; となります。ここで、ラムダ式の中で getLine >>= \y ... と続けると、do 構文の中では x <- getLine; y <- getLine; ... となります。do 構文の return はモナドの return と同じです。

IO モナドだけではなく、ほかのモナドでも do 構文を使うことができます。簡単な例を示します。

ghci> do { x <- Just 1; y <- Just 2; return (x, y)}
Just (1,2)
ghci> do {x <- [1,2,3]; y <- "abc"; return (x, y)}
[(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c'),(3,'a'),(3,'b'),(3,'c')]

モナドの演算子 >> は左辺が渡す値を無視して、右辺のモナドを返します。簡単な例を示します。

ghci> Just 1 >> Just 2
Just 2
ghci> Nothing >> Just 2
Nothing
ghci> [1,2,3] >> [4,5,6]
[4,5,6,4,5,6,4,5,6]
ghci> [] >> [4,5,6]
[]
ghci> [y | _ <- [1,2,3], y <- [4,5,6]]
[4,5,6,4,5,6,4,5,6]
ghci> [y | _ <- [1,2,3], y <- []]
[]

Just 1 >> Just 2 は Just 1 >>= \_ -> Just 2 と同じ意味で、左辺から渡される値 2 を捨てるだけです。左辺値が Nothing であれば、今までと同じく Nothing を返します。リストモナドの場合、リスト内包表記で [1,2,3] の要素を捨てることと同じ動作になります。

また、次のように左辺から右辺に渡す値が不要な場合、演算子 >> を使うことができます。

ghci> getLine >>= \x -> print x >> print (reverse x)
hello, world
"hello, world"
"dlrow ,olleh"

>> print (reverse x) は >>= \_ -> print (reverse x) と同じです。もちろん、do 構文でも同じことができます。

ghci> do { x <- getLine; print x; print (reverse x)}
hello, world
"hello, world"
"dlrow ,olleh"

print x の返り値 IO () は捨てられて、print (reverse x) が実行されます。

●guard と MonadPlus

次は、リスト内包表記の条件節をモナドで実現してみましょう。次の例を見てください。

ghci> [x | x <- [1..10], even x]
[2,4,6,8,10]
ghci> [1..10] >>= \x -> if even x then return x else []
[2,4,6,8,10]

リストモナドは concatMap でリストを連結します。このとき、空リストは無視されるので、リストに格納された値だけが連結されて返されます。

次のように、モナドの途中で if の処理を行うこともできます。

ghci> [1..10] >>= \x -> (if even x then [()] else []) >> return x
[2,4,6,8,10]
ghci> do { x <- [1..10]; if even x then [()] else []; return x}
[2,4,6,8,10]

左辺が空リストの場合、リストモナドは空リストを返すことを利用しています。したがって、モナドで連結した処理の途中で空リストが返されると、それ以降の処理は結果が空リストになるのです。空リスト以外の値、たとえば、unit 型を格納したリストを返すと、それ以降の処理が実行されて、条件を満たすデータがリストに格納されて返されます。do 構文を使った場合も同じです。

この処理はモジュール Control.Monad に定義されている関数 guard を使うと簡単です。guard の型を :t コマンドで調べてみると、次のように表示されます。

ghci> :m + Control.Monad
ghci> :i guard
guard :: GHC.Base.Alternative f => Bool -> f ()
        -- Defined in ‘Control.Monad’

guard には型クラス制約 Alternative が付けられています。:i コマンドで Alternative を調べてみましょう。

ghci> :i GHC.Base.Alternative
type GHC.Base.Alternative :: (* -> *) -> Constraint
class Applicative f => GHC.Base.Alternative f where
  GHC.Base.empty :: f a
  (GHC.Base.<|>) :: f a -> f a -> f a
  GHC.Base.some :: f a -> f [a]
  GHC.Base.many :: f a -> f [a]
  {-# MINIMAL empty, (<|>) #-}
        -- Defined in ‘GHC.Base’
instance GHC.Base.Alternative IO -- Defined in ‘GHC.Base’
instance GHC.Base.Alternative [] -- Defined in ‘GHC.Base’
instance GHC.Base.Alternative Maybe -- Defined in ‘GHC.Base’

Alternative は Applicative を継承していて、単位元 empty と二項演算子 <|> の仕様が定義されています。つまり、Alternative は Applicative の Monoid バージョンなのです。Maybe とリストの場合、Alternative は次のように定義されています。

リスト : Maybe とリストの Alternative

instance Alternative Maybe where
  empty = Nothing
  Nothing <|> r = r
  l       <|> _ = l

instance Alternative [] where
  empty = []
  (<|>) = (++)

Maybe の場合、Monoid のデータ型 First と同じで、<|> は論理和 (||) のように短絡演算子として機能します。リストは Monoid の定義と同じです。

関数 guard は Alternative を使って次のように定義されています。

リスト : 関数 guard の定義

guard :: (Alternative f) => Bool -> f ()
guard True  =  pure ()
guard False =  empty

guard は引数が真ならば pure () を返し、そうでなければ empty を返します。リストの場合、empty は空リストなので、それ以降のリストモナドの処理は結果が空リストになり、guard はガードとして機能します。

簡単な実行例を示します。

ghci> [1..10] >>= \x -> guard(even x) >> return x
[2,4,6,8,10]
ghci> do {x <- [1..10]; guard(even x); return x}
[2,4,6,8,10]

このほかに、Control.Monad には Alternative と Monad を継承した型クラス MonadPlus も用意されています。

ghci> :i MonadPlus
type MonadPlus :: (* -> *) -> Constraint
class (GHC.Base.Alternative m, Monad m) => MonadPlus m where
  mzero :: m a
  mplus :: m a -> m a -> m a
        -- Defined in ‘GHC.Base’
instance MonadPlus IO -- Defined in ‘GHC.Base’
instance MonadPlus [] -- Defined in ‘GHC.Base’
instance MonadPlus Maybe -- Defined in ‘GHC.Base’

mzero が単位元、mplus が二項演算子を表します。デフォルトの定義は Alternative の empty と <|> が使われています。

●順列の生成

それでは簡単な例題として、リストモナドを使って順列を生成する関数 permutation n xs を作ってみましょう。permutation はリスト xs から n 個の要素を選択して順列を生成します。プログラムは次のようになります。

リスト : 順列の生成

permutation :: Eq a => Int -> [a] -> [[a]]
permutation n xs = iter 0 [] where
  iter m ys
    | m == n    = return (reverse ys)
    | otherwise = do
        x <- xs
        guard(x `notElem` ys)
        iter (m + 1) (x:ys)

実際の処理は局所関数 iter で行います。引数 m が選んだ要素の個数、ys が選んだ要素を格納するリストです。m が n と等しい場合、順列が一つ完成したので、reverse で ys を反転してから return でリストに格納します。そうでなければ、xs から要素 x を一つ選び、guard で x が ys に含まれていないことを確認して、iter を再帰呼び出しします。

それでは実行してみましょう。

ghci> permutation 2 [1,2,3,4]
[[1,2],[1,3],[1,4],[2,1],[2,3],[2,4],[3,1],[3,2],[3,4],[4,1],[4,2],[4,3]]
ghci> permutation 3 [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
ghci> permutation 3 [1,2,3,4]
[[1,2,3],[1,2,4],[1,3,2],[1,3,4],[1,4,2],[1,4,3],[2,1,3],[2,1,4],[2,3,1],[2,3,4]
,[2,4,1],[2,4,3],[3,1,2],[3,1,4],[3,2,1],[3,2,4],[3,4,1],[3,4,2],[4,1,2],[4,1,3]
,[4,2,1],[4,2,3],[4,3,1],[4,3,2]]

●経路の探索

モナドを使うと、「経路の探索 (2)」の "探索の一般化" で作成した関数 search と search' を一つのプログラムにまとめることができます。経路図とプログラムを再掲します。

    Ｂ------Ｄ------Ｆ
  ／│      │          
Ａ  │      │          
  ＼│      │          
    Ｃ------Ｅ------Ｇ

      図 :経路図

リスト : 経路の探索

-- 隣接リスト
adjacent :: [[Int]]
adjacent =
  [[1,2],
   [0,2,3],
   [0,1,4],
   [1,4,5],
   [2,3,6],
   [3],
   [4]]

-- 次の頂点へ進む
nextPath :: [Int] -> [[Int]]
nextPath path@(x:xs) = [y:path | y <- adjacent !! x, y `notElem` xs]

-- 解をリストに格納して返す
search :: (a -> Bool) -> (a -> b) -> (b -> [a] -> [a]) -> [a] -> [a]
search _ _ _ [] = []
search isGoal nextState combine (x:xs) =
  if isGoal x then x : search isGoal nextState combine xs
  else search isGoal nextState combine (combine (nextState x) xs)

-- 解を一つだけ求める
search' :: (a -> Bool) -> (a -> b) -> (b -> [a] -> [a]) -> [a] -> Maybe a
search' _ _ _ [] = Nothing
search' isGoal nextState combine (x:xs) =
  if isGoal x then Just x 
  else search' isGoal nextState combine (combine (nextState x) xs)

リストと Maybe を MonadPlus として扱うと、search と search' のデータ型は次のように表すことができます。

searchM :: MonadPlus m => (a -> Bool) -> (a -> b) -> (b -> [a] -> [a]) -> [a] -> m a

関数名は searchM としました。searchM の返り値の型を m a とし、型クラス制約 に MonadPlus m を指定します。すると、searchM の返り値は MonadPlus のインスタンスになります。プログラムは次のようになります。

リスト : モナドで統一する

searchM :: MonadPlus m => (a -> Bool) -> (a -> b) -> (b -> [a] -> [a]) 
-> [a] -> m a
searchM _ _ _ [] = mzero
searchM isGoal nextState combine (x:xs) =
  if isGoal x then return x `mplus` searchM isGoal nextState combine xs
  else searchM isGoal nextState combine (combine (nextState x) xs)

-- 深さ優先探索
dfsM :: Int -> Int -> [[Int]]
dfsM start goal =
  searchM (\x -> head x == goal) nextPath (++) [[start]]

dfsM' :: Int -> Int -> Maybe [Int]
dfsM' start goal =
  searchM (\x -> head x == goal) nextPath (++) [[start]]

-- 幅優先探索
bfsM :: Int -> Int -> [[Int]]
bfsM start goal =
  searchM (\x -> head x == goal) nextPath (flip (++)) [[start]]

bfsM' :: Int -> Int -> Maybe [Int]
bfsM' start goal =
  searchM (\x -> head x == goal) nextPath (flip (++)) [[start]]

searchM で最後の引数が空リストの場合、MonadPlus の mzero を返します。リストの場合は空リストが、Maybe の場合は Nothing が返されます。x がゴールに到達した場合、return x でモナドに格納し、mplus で searchM の返り値と連結します。

リストの場合、mplus は演算子 ++ なので、見つけた解をリストに格納して返す動作になります。Maybe の場合、mplus は論理和と同じ動作になるので、ここで探索が打ち切られて Just x が返されます。あとは、searchM を使って深さ優先探索を行う関数 dfsM, dfsM' と幅優先探索を行う関数 bfsM, bfsM' を定義するだけです。

簡単な実行例を示します。

ghci> fmap reverse $ dfsM 0 6
[[0,1,2,4,6],[0,1,3,4,6],[0,2,1,3,4,6],[0,2,4,6]]
ghci> dfsM' 0 6
Just [6,4,2,1,0]
ghci> fmap reverse $ dfsM' 0 6
Just [0,1,2,4,6]
ghci> fmap reverse $ bfsM 0 6
[[0,2,4,6],[0,1,2,4,6],[0,1,3,4,6],[0,2,1,3,4,6]]
ghci> fmap reverse $ bfsM' 0 6
Just [0,2,4,6]

●リストモナドと非決定性計算

Maybe の Nothing が「失敗」を表すことができるように、リストの空リストも失敗を表すことができます。逆に、ある計算が「成功」した場合、Maybe は結果を Just で表すことができます。リストの場合、複数の要素が格納されているので、どの要素が成功するのかわかりませんが、この中に計算が成功する要素が含まれていると考えます。

そこで、リストの中から要素を一つ選ぶ処理を考えます。たとえば、ls !! n はリスト ls の n 番目の要素を取り出しますが、選ぶ要素を引数 n で指定する必要があります。これに対して、特別な指定をしないで無作為に要素を選ぶことを考えます。このような選択を「非決定的選択」といいます。

ここで、非決定的選択は問題を解くのに都合のいい選択が行われると仮定します。つまり、複数の選択肢の中で解に導くものがいくつか存在するならば、そのうちの一つを選択するのです。たとえば、迷路で分かれ道にきた場合、その中から出口につながる道を一つ選ぶわけです。このような非決定的選択を含む処理 (計算) を「非決定性計算」とか「非決定性」といいます。

このような都合のいい処理を現在のコンピュータで実現することは不可能ですが、バックトラックを使って近似的に実現することは可能です。つまり、ある要素を選んで条件を満たさない場合は、バックトラックして異なる要素を選択すればいいわけです。Haskell の場合、リストモナドはすべての組み合わせを生成するように動作するので、その中から条件を満たす解を探せばいいわけです。

このように、リストモナドは「非決定性計算」をシミュレートしていると考えることができます。また、Haskell は遅延評価により必要になったときに新しい組み合わせを生成するので、多くのメモリを消費することなく効率的に処理することができます。

●論理パズル

簡単な例題として論理パズルを解いてみましょう。

簡単な論理パズルなので、プログラムを作る前に考えてみてください。

●データ型の定義

最初に必要となるデータ型を定義しましょう。

リスト : データ型の定義

data Nation = US | IL | AU deriving (Eq, Show)
data Sports = Basket | Cricket | Tennis deriving (Eq, Show)
data Name   = Michael | Simon | Richard deriving (Eq, Show)
data Person = Person {name :: Name, rank :: Int, nation :: Nation, sports :: Sports} 
deriving Show

このデータをリストモナドで作成します。次のリストを見てください。

リスト : データの生成

makePerson :: Name -> [Person]
makePerson name = do
  r <- [1, 2, 3]
  n <- [US, IL, AU]
  s <- [Basket, Cricket, Tennis]
  return (Person name r n s)

<- で順位 (1, 2, 3)、国籍 (US, IL, AU)、スポーツ (Basket, Cricket, Tennis) の中から要素を一つ選びます。Haskell は遅延評価を行うので、データが必要になるときに異なる要素が選ばれて、新しいデータが生成されます。

●補助関数の作成

次は問題を解くための補助関数を作ります。

リスト : 補助関数の定義

-- 国籍を探す
findNation :: Nation -> [Person] -> Person
findNation _ [] = error "findNation"
findNation x (y:ys) =
  if x == nation y then y else findNation x ys

-- スポーツを探す
findSports :: Sports -> [Person] -> Person
findSports _ [] = error "findSports"
findSports x (y:ys) =
  if x == sports y then y else findSports x ys

-- 名前以外で重複した要素があるか
isDuplicate :: Person -> Person -> Bool
isDuplicate x y =
  rank x == rank y || nation x == nation y || sports x == sports y

-- 同じ要素があるか
check :: Person -> Person -> Person -> Bool
check a b c = isDuplicate a b || isDuplicate a c || isDuplicate b c

findNation は引数のリスト中から国籍が x と等しい要素を返します。findSports は好きなスポーツが x と等しい要素を返します。isDuplicate は引数 a と b に重複した要素があれば True を返します。要素が全て異なる場合は False を返します。関数 check は isDuplicate を呼び出して、引数 a, b, c に重複した要素があれば True を返します。

●論理パズルの解法

論理パズルの解法プログラムは次のようになります。

リスト : 論理パズルの解法

solver :: [[Person]]
solver = do
  m <- makePerson(Michael)
  s <- makePerson(Simon)
  r <- makePerson(Richard)
  guard(not(check m s r))
  guard(sports m == Basket)
  guard(nation m /= US)
  guard(nation s == IL)
  guard(rank m < rank(findNation US [m,s,r]))
  guard(rank s < rank(findSports Tennis [m,s,r]))
  guard(rank(findSports Cricket [m,s,r]) == 1)
  return [m,s,r]

最初に makePerson でデータを作成し、<- で要素を一つ選んで局所変数 m, s, r にセットします。そして、check で順位、国籍、スポーツで要素が重複していないかチェックします。あとは問題の条件を guard でチェックしていくだけです。

1. Michael の好きなスポーツはバスケットである。
2. Michael の国籍はアメリカではない。
3. Simon の国籍はイスラエルである。
4. Michael は国籍がアメリカの人よりも上位である。
5. Simon はテニスが好きな人よりも上位である。
6. クリケットが好きな人が１位である。

最後に、return で見つけた解をリストに格納します。とても簡単ですね。実行結果は次のようになります。

ghci> solver
[[Person {name = Michael, rank = 2, nation = AU, sports = Basket},
  Person {name = Simon,   rank = 1, nation = IL, sports = Cricket},
  Person {name = Richard, rank = 3, nation = US, sports = Tennis}]]

解は 1 通りで、１位が Simon, ２位が Michael, ３位が Richard になります。ちなみに、最後の条件がない場合は 2 通りの解が出力されます。興味のある方は試してみてください。

●モナドとパターンマッチング

モナドの演算子 >>= の右辺は通常の関数なので、引数にパターンマッチングを使うことができます。パターンマッチングに失敗した場合、演算子 >>= と do 構文 (リスト内包表記) では動作が異なります。

簡単な例を示しましょう。

ghci> Just "abcd" >>= \('a':s) -> return ('a', s)
Just ('a',"bcd")
ghci> Just "Abcd" >>= \('a':s) -> return ('a', s)
*** Exception: :3:17-43: Non-exhaustive patterns in lambda

ghci> ["abcd"] >>= \('a':s) -> return ('a', s)
[('a',"bcd")]
ghci> ["Abcd"] >>= \('a':s) -> return ('a', s)
*** Exception: :5:14-40: Non-exhaustive patterns in lambda

演算子 >>= の場合、パターンマッチングで失敗するとエラーが送出されます。ところが、do 構文の場合は Monad の関数 fail が呼び出されます。次の例を見てください。

ghci> do { ('a':s) <- Just "abcd"; return ('a', s) }
Just ('a',"bcd")
ghci> do { ('a':s) <- Just "Abcd"; return ('a', s) }
Nothing
ghci> do { ('a':s) <- ["abcd"]; return ('a', s) }
[('a',"bcd")]
ghci> do { ('a':s) <- ["Abcd"]; return ('a', s) }
[]

Maybe モナドの fail は Nothing を返すので、do の返り値は Nothing となります。同様に、リストモナドの fail は空リストを返すので、do の返り値は空リストになります。Maybe モナドとリストモナドの文脈が、失敗するかもしれない計算を表していると考えると、エラーを送出するよりも Nothing や空リストを返したほうが都合が良いことがあります。

●リストモナドと reads

関数 reads とリストモナドを組み合わせると簡単な構文解析を行うことができます。reads の型をコマンド :t で調べると次のように表示されます。

ghci> :t read
read :: Read a => String -> a
ghci> :t reads
reads :: Read a => ReadS a
ghci> :i ReadS
type ReadS :: * -> *
type ReadS a = String -> [(a, String)]
        -- Defined in `Text.ParserCombinators.ReadP'

型クラス制約に Read が指定されています。型クラス Read のインスタンスは、関数 read や reads を使って文字列をそのデータ型に変換することができます。

簡単な例を示しましょう。

ghci> read "123" :: Int
123
ghci> read "123.456" :: Double
123.456
ghci> read "'a'" :: Char
'a'
ghci> read "\"hello, world\"" :: String
"hello, world"
ghci> read "[1,2,3,4]" :: [Int]
[1,2,3,4]
ghci> read "123 456" :: Int
*** Exception: Prelude.read: no parse

関数 read は構文解析に失敗するとエラーを送出しますが、そうしたくない場合は関数 reads を使います。簡単な例を示します。

ghci> reads "123 456" :: [(Int, String)]
[(123," 456")]
ghci> reads "123456" :: [(Int, String)]
[(123456,"")]
ghci> reads "    123456" :: [(Int, String)]
[(123456,"")]
ghci> reads "123.456" :: [(Int, String)]
[]

reads は変換した値とそれ以降の文字列をタプルにセットし、それをリストに格納して返します。reads は空白文字を区切り記号として扱うので、先頭の空白文字は読み飛ばしてくれます。構文解析に失敗した場合は空リストを返します。これはリストモナドと組み合わせるときに役に立ちます。

それでは簡単な例題として文字列から「二分木」を生成する関数 readsTree を作ってみましょう。二分木のデータ型を再掲します。

リスト : 二分木のデータ型

data Tree a = Nil | Node a (Tree a) (Tree a) deriving Show

この二分木を次のような文字列で表すことにします。

Nil => #
Node 1 Nil Nil => <1##>
Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil) => <2<1##><3##>>

Nil は '#' で、Node は <...> で表します。

プログラムは次のようになります。

リスト : 二分木の読み込み

readsTree :: Read a => ReadS (Tree a)
readsTree "" = []
readsTree ('#':s) = return (Nil, s)
readsTree ('<':s) = do
  (x, t) <- reads s
  (l, u) <- readsTree t
  (r, '>':v) <- readsTree u
  return (Node x l r, v)
readsTree (_:s) = readsTree s

readsTree の引数は文字列です。空文字列の場合は空リストを返します。先頭の文字が '#' であれば return で (Nil, s) をリストに格納します。次に、先頭の文字が '<' であれば、reads で二分木の要素を読み込みます。次に、左部分木を readsTree で読み込み、最後に右部分木を readsTree で読み込み、return で (Node x l r, v) をリストに格納します。ここで、帰ってきた文字列の先頭文字が '>' であることを確認します。そうでなければマッチングに失敗して返り値は空リストになります。最後の節で、'#' と '<' 以外の文字はスキップします。

簡単な実行例を示します。

ghci> readsTree "#" ::[(Tree Int, String)]
[(Nil,"")]
ghci> readsTree "<2##>" ::[(Tree Int, String)]
[(Node 2 Nil Nil,"")]
ghci> readsTree "<2<1##>#>" ::[(Tree Int, String)]
[(Node 2 (Node 1 Nil Nil) Nil,"")]
ghci> readsTree "<2<1##><3##>>" ::[(Tree Int, String)]
[(Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil),"")]
ghci> readsTree "<2<1##>>3.1##>>" ::[(Tree Int, String)]
[]
ghci> readsTree "<2<1##><3##" ::[(Tree Int, String)]
[]

なお、型クラス Read は deriving することができるので、二分木に deriving で Read を指定すると、read や reads で二分木を読み込むことができます。

簡単な実行例を示します。

リスト : 二分木のデータ型 (2)

data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Read, Show)

ghci> read "Nil" :: Tree Int
Nil
ghci> read "Node 1 Nil Nil" :: Tree Int
Node 1 Nil Nil
ghci> read "Node 2 (Node 1 Nil Nil) Nil" :: Tree Int
Node 2 (Node 1 Nil Nil) Nil
ghci> read "Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)" :: Tree Int
Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)