Inside Parsec

<|> パーサコンビネータ

<|> パーサコンビネータ

<|> パーサコンビネータは２つのモナドの選択を表すモナドを作成する。つまり、 

m <|> n

は、m のパターンマッチが成功するか、n のパターンマッチが成功したときマッチ成功の値を返す。両方のパターンマッチが失敗したとき、マッチエラーの値を返す。

<|> コンビネータの定義は次のようになる。 

(<|>) :: (ParsecT s u m a) -> (ParsecT s u m a) -> (ParsecT s u m a)
p1 <|> p2 = mplus p1 p2

mplus は MonadPlus クラスの多相関数だ。Monad クラスのインスタンスは mplus 演算子についてモノイドである。要するに冒頭に述べた性質を持つ。数学の表現が入るとわかりにくいが、Haskell で数学が入ってくるときはたいてい多相関数のことだと思えば良い。色々な型で共通の演算のことだ。

モナドクラス

モナドクラスのインスタンスは mzero という値と、mplus p1 p2 という演算子を持っていなければならないが、<|> の動作を知るためには詮索する必要はない。 

instance MonadPlus (ParsecT s u m) where
    mzero = parserZero
    mplus p1 p2 = parserPlus p1 p2

ParsecT モナドのときは mzero は parserZero で定義される。parserZero は (unParser parserZero) 関数の継続の引数のうち eerr のみが使われている。つまり、いつでも eerr の値を返す。 

parserZero :: ParsecT s u m a
parserZero
    = ParsecT $ \s _ _ _ eerr ->
      eerr $ unknownError s

parserPlus 関数

<|> コンビネータの定義の実体は次の parserPlus 関数だ。これは２つの ParsecT モナド m と n を引数にとり、ParsecT モナドを値として返す。 

parserPlus :: ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
{-# INLINE parserPlus #-}
parserPlus m n
    = ParsecT $ \s cok cerr eok eerr ->
      let
          meerr err =
              let
                  neok y s' err' = eok y s' (mergeError err err')
                  neerr err' = eerr $ mergeError err err'
              in unParser n s cok cerr neok neerr
      in unParser m s cok cerr eok meerr

ParserPlus m n = p と置くと、 

(unParser p) = \s cok cerr eok eerr -> unParser m s cok cerr eok meerr

である。次のように書いてもよい。 

(unParser p) s cok cerr eok eerr = (unParser m) s cok cerr eok meerr

この関数では m のパターンマッチが成功した場合は cok または eok が実行されて値として返される。m のパターンマッチが失敗したとき、入力の消費が起きていればやはり cerr が実行されて p の値が決定される。パターンマッチが失敗し、入力の消費もおこなかったときは、meerr が実行されて処理が継続する。

meerr の定義は次のようになっている。 

meerr err = unParser n s cok cerr neok neerr

これは次のように書いたほうが分かりやすい。 

meerr err = (unParser n) s cok eerr neok neerr

パターンマッチが成功し (unParser n) で消費が起きたときは、cok が実行されて値が返される。パターンマッチが失敗し、消費が起きたときは、eerr が実行される。これは m と n が共に失敗した場合だ。

n のパターンマッチが成功し消費が起きなかった場合は neok が実行される。neok は次のように定義されている。 

neok y s' err' = eok y s' (mergeError err err')

n のパターンマッチで発生した y s' と m と n の ParserError をマージしたものを eok に渡して値を返している。

n のパターンマッチが失敗し消費が起きなかった場合は、neerr が実行される。neerr は次のように定義されている。 

neerr err' = eerr $ mergeError err err'

これは、単に m と n のパターンマッチの両者で発生した ParseError をマージして返しているだけだ。

継続渡しスタイル

parserPlus のコードは継続渡しスタイルの利点をよく表している。多分岐が階層的に行われているが、値の処理を継続に移譲しているために、値のリターンが発生せず、分岐の階層を自然に記述していくことができる。また、この際分岐のモジュール化ができる。

ちょっと実験してみた。

cont.hs は文字列の引数と ok 処理 err 処理を引数とする継続スタイルの２つのパーサ foo, bar を記述している。test 関数は err にプログラムされた関数を渡すことで foo, bar の２つのパーサの選択を記述している。 

cont.hs

foo :: String -> (String -> String) -> (String -> String) -> String
foo input ok err | input == "foo" = ok "Ok" | otherwise = err input
bar input ok err | input == "bar"= ok "Ok" | otherwise = err input

pok msg = msg; perr _ = "Error"

test input = foo input (pok) (\e -> bar e (pok) (perr))
実行例 
*Main> test "foo"
"Ok"
*Main> test "bar"
"Ok"
*Main> test "baz"
"Error"