LoginSignup
1

More than 3 years have passed since last update.

リストモナドについて

Last updated at Posted at 2020-03-22

TL;DR;

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

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

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

Haskellのリストについて

非決定的な値である

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

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

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

リストモナド
instance Monad [] where
    return x [x]
    xs >>= f = concat (map f xs) -- xs:: [a], f:: a->[b]

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

  • 中置関数である
  • 2つの引数を受け取り、それぞれの引数の型は以下である
    • 第1引数: xs:: [a]
    • 第2引数: 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])から、さらにより多くの値が生成されている。

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

騎士の旅

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

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

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

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

-- ナイトの現在位置を表す型
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')

-- 3手先の候補を導出する関数
in3 :: KnightPos -> [KnightPos]
in3 start = do
    first <- moveKnight start
    second <- moveKnight first
    moveKnight second

{- 以下do記法を使わず書いた場合
in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight
-}


-- 3手先にその候補が含まれているかどうか求める関数
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 騎士の旅

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1