第8章 関数型パーサー #2

連結

今度はバインド演算子 (>>=)が出てきた。 教科書では、この演算子は「そして」と読めばいいと書いてある。教科書の付録Bには、この演算子の意味は“順序付け”だとある。その真意は後から分かってくる。

(>>-) :: Parser a -> (a -> Parser b) -> Parser b
p >>- f = \inp -> case parse p inp of
                    [] -> []
                    [(v, out)] -> parse (f v) out

上の定義に出てくるpは1つ目のパーサー、fは「1つ目のパーサーのパース結果を前提にした2つ目のパーサー」ととらえればいい。演算結果は、1つ目のパーサーと2つ目のパーサーを実際に連結したパーサーだ（型は2つめのパーサーと同じ型になる）。 右辺のinpは入力文字列。入力文字列を1つ目のパーサーに食わせた結果がparse p inpで、その結果を元にパターンマッチで分岐している。落ち着いて読めば難しくはない。

そして、このバインド演算子の連続適用方法が説明される。

p1 >>= \v1 ->
p2 >>= \v2 ->
...
pn >>= \vn ->
return (f v1 v2 ... vn)

でもこれちょっと端折ってるなあ。最初はこのバインド演算子の使い方として、「右辺をラムダ式にすると便利」という所からにしてほしい。つまり、

p1 >>= (\v1 -> return (f v1))

の右辺は、「左辺のパース結果をv1としたときの、最終的なパーサー」で、かつバインド演算子の優先順位は低いから右辺の括弧は省略できて、

p1 >>= \v1 -> return (f v1)

と書ける。そしてこのときには、「p1の結果をバインド演算子によってv1に結びつけたとき、最終的なパース結果はv1の関数になる。」という意味になる。

ここで初めてバインド演算子の連続適用（というか、入れ子適用）の話をすればいい。

パーサー p1とp2があったとき、p1とp2を結合するには

p1 >>= \v1 -> (p2 >>= \v2 -> return (f v1 v2))

と書くけれども、ここでもバインド演算子の優先順位は低いから右辺の括弧は省略できて、

p1 >>= \v1 -> p2 >>= \v2 -> return (f v1 v2)

と書ける。これを改行して見やすくしたものが

p1 >>= \v1 ->
p2 >>= \v2 ->
return (f v1 v2)

で、これの意味は、「p1の結果をバインド演算子によってv1に結びつけ、そしてその次にp2の結果をバインド演算子によってv2に結びつけたとき、最終的なパース結果はv1とv2の関数になる。」だ。ここまで説明すれば、パーサの数がn個になったときの書き方もすぐ理解できると思う。

さて、話は次に進んで、do記法だ。

do v1 <- p1
   v2 <- p2
   ...
   vn <- pn
   return (f v1 v2 ... vn)

と、Haskellではこのように書けると出てくるのだけど、ここが地味に嘘で、そのためには本物のモナドを使う必要がある。 もともと、returnや>>=も本物のモナド用の関数・演算子なので、この章では使えない。それを知っていたので、わざとその代わりにreturn'や>>-を定義してみたのだけど、さすがにdo記法だけは対応できない。まあ、10章まで待ちます。

さて、教科書はこの後はdo記法で書かれているけど、Hugsで動かしたいので、do記法を使わずに、おれおれ>>-とおれおれreturn'で写経する。

p :: Parser (Char, Char)
p = item >>- \x ->
    item >>- \_ ->
    item >>- \y ->
    return' (x, y)

do記法だと使用しない値は変数にバインドしなくていいけど、バインド演算子で書く場合には省略できないのがちょっと残念。

選択

これはor、っていうか||演算子に似ている。

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = \inp -> case parse p inp of
                    [] -> parse q inp
                    [(v, out)] -> [(v, out)]