Prev: Error モナド TOC: 目次 Next: IO モナド

List モナド

概観
計算のタイプ: ゼロ個以上の可能な結果を返す計算
束縛戦略: 束縛された関数は入力リストのすべての可能な値に対して適用されます。 結果のリストはすべての可能な結果リストを生成するために連結されます。
利用場面: 非決定性のある演算の並びからの計算の構築。曖昧な文法のパースを するというのがよくある例です。
ゼロとプラス [] がゼロで、++ がプラス演算
型の例: [a]

動機

List モナドは非決定性をもつ計算の連鎖を、演算をそれぞれのステップで 可能なすべての値に適用することで、合成する戦略を内包しています。これは 計算が曖昧性を扱わなければならないときに有用です。そのような場合、すべて の可能性を、曖昧性が解決するまで、探索することを可能にします。

定義

 
instance Monad [] where
    m >>= f  = concatMap f m
    return x = [x]
    fail s   = []
    
instance MonadPlus [] where
    mzero = []
    mplus = (++)

例

Listモナドの使い方の標準的な例は、曖昧な文法のパースです。以下の例は データをパースして16進数、10進数、英数字だけを含む単語にするだけの ものです。16進数文字は10進数文字と英数字文字と重複していて、曖昧な 文法になっていることに注意してください。たとえば、"dead" は 16進数であり、 通常の単語でもありますし、"10" は10の10進数表現でもあり、16の16進数 表現でもあります。

example13.hs で利用できるコード 
-- 3つの異るタイプの項をパースできます
data Parsed = Digit Integer | Hex Integer | Word String deriving Show

-- パースされた16進数の表現に一文字を追加する
parseHexDigit :: Parsed -> Char -> [Parsed]
parseHexDigit (Hex n) c = if isHexDigit c then
                            return (Hex ((n*16) + (toInteger (digitToInt c))))
                          else
                            mzero
parseHexDigit _       _ = mzero

-- パースされた10進数の表現に一文字を追加する
parseDigit :: Parsed -> Char -> [Parsed]
parseDigit (Digit n) c = if isDigit c then
                           return (Digit ((n*10) + (toInteger (digitToInt c))))
                         else
                           mzero
parseDigit _         _ = mzero
		   
-- パースされた単語表現に一文字を追加する
parseWord :: Parsed -> Char -> [Parsed]
parseWord (Word s) c = if isAlpha c then
                         return (Word (s ++ [c]))
                       else
                         mzero
parseWord _        _ = mzero

-- (数)字を16進数の値、10進数の値、単語の値としてパースすることを試みる
-- the result is a list of possible parses
parse :: Parsed -> Char -> [Parsed]
parse p c = (parseHexDigit p c) `mplus` (parseDigit p c) `mplus` (parseWord p c)

-- 文字列全体をパースし、可能なパース値のリストを返す
parseArg :: String -> [Parsed]
parseArg s = do init <- (return (Hex 0)) `mplus` (return (Digit 0)) `mplus` (return (Word ""))
                foldM parse init s
Prev: Error モナド TOC: 目次 Next: IO モナド