リストモナドについて

TL;DR;

リストモナドは、非決定的な値 と 非決定性計算 からさらにより多くの非決定的な値を生成する非決定性計算です

非決定性計算と非決定的な値とは

関数型プログラミングでは、
０個を含む複数の値を返す関数 のことを、 非決定性計算 と呼びます。
また０個を含む複数の値、そのものを一つの値と見なしたものを 非決定的な値 と呼びます。

Haskellのリストについて

非決定的な値である

Haskellのリストは複数の値を保持する事ができるので、非決定的な値としてリストが用いられています。

モナドのインスタンスである

またリストは以下のようにモナドのインスタンスとして定義されています。

リストモナド

instance Monad [] where
	return x [x]
	xs >>= f = concat (map f xs) -- xs:: [a], f:: a->[b]

上記から、リストモナドの >>= 関数は、以下のことが言えます。
(※ >>= は　bind と呼びます)

• 中置関数である
• ２つの引数を受け取り、それぞれの引数の型は以下である
  • 第１引数: xs:: [a]
  • 第２引数: f:: a -> [b]
• map f xs の出力値は、二重リスト [[b]] である
• >>=関数は、map f xs の出力結果をconcat関数で一つのリストに結合した結果を返す

つまりリストモナドとは

非決定的な値(xs:: [a]) と 非決定性計算(f:: a->[b]) を引数にとり、さらにより沢山の候補値を含んだ非決定的な値を返す関数(非決定性計算)であると言えます。

リストモナドを使った簡単な問題

入力された数字の正数と負数を求める

リストモナドのサンプル

ghci> [3,4,5] >>= \x -> [x, -x]
[3,-3,4,-4,5,-5]

非決定的な値([3,4,5])と非決定計算(\x->[x,-x])から、さらにより多くの値が生成されている。

騎士の旅をリストモナドを使って解く

騎士の旅

チェス盤の上にナイトのコマが一つだけ乗っており、ナイトを３回動かして特定のマスまで移動させることが出来るか？

ヒント
ナイトの次の位置は複数の候補が存在し、その関数は非決定性計算になる。

リストモナドを使った解答例

リストモナドを使って騎士の旅を解く

-- ナイトの現在位置を表す型
type KnightPos = (Int, Int)

-- 騎士の次の位置の候補を返す関数 (非決定計算である)
moveKnight :: KnightPost -> [KnightPos]
moveKnight (c, r) = do
	(c', r') <- [(c+2, r-1), (c+2, r+1), (c-2, r-1), (c-2, r+1), (c+1, r-2), (c-1,r-2), (c-1, r+2)]
	guard (c' `elem` [1..8] && r' `elem` [1..8])
	return (c', r')
	
-- ３手先の候補を導出する関数
in3 :: KnightPos -> [KnightPos]
in3 start = do
	first <- moveKnight start
	second <- moveKnight first
	moveKnight second
	
{- 以下do記法を使わず書いた場合
in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight
-}


-- ３手先にその候補が含まれているかどうか求める関数
canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start

動作結果

ghci

ghci> (6, 2) `canReachIn3` (6, 1)
True
ghci> (6, 2) `canReachIn3` (7, 3)
False

参考サイト

A knight's quest

書籍

上記参考サイトの日本語訳が以下の書籍で紹介されています。

すごいHaskellたのしく学ぼう! 単行本（ソフトカバー） – 2012/5/23

p306 騎士の旅