Parsec3 におけるパーサーの型

きっかけは try

いつものように Parsec2 で安穏とパーサーを書き始めたのですが、 try が増えそうな気配だったこともあり、これを期に「Applicative！ Parsec3！」と思い立ちました。とっかかりとして、『Real World Haskell』 16章の例を Parsec3 で試してみることにします。

import Control.Applicative hiding ((<|>))
import Text.Parsec

parser = (++) <$> string "HT" <*> (string "TP" <|> string "ML")

Parsec2 だと、 RWH に堂々と「Parsec プログラマは型宣言を省略するのが通常になってます」と書いてあったりして、パーサーの型シグネチャをはしょって生きてきました。その感覚でこのコードをコンパイルしたところ、こんなクレームが。

No instance for (Stream s m Char)
  arising from a use of `string'

はて、(Stream s m Char)ってなんだろう。調べてみると、 NoMonomorphismRestriction なる言語拡張を導入すれば解決するらしい（参照）。いわれるままソースの冒頭に {-# LANGUAGE NoMonomorphismRestriction #-} という行を追加すると、確かにコンパイルに通ります。なにこのおまじない。。

単相性制限

憤慨していたら @bonotake さんからヒントをもらいました（ありがとうございます）。

型定義が与えられていない関数の型を推論する際に、多相的な型が想定できる場合でもデフォルトの型（Integerなど）に決めうちする、という規則らしいです。そのオプションを指定するか、型定義を忘れず自分で書けｗ ということらしい
http://twitter.com/#!/bonotake/status/108445024378818562

つまり型推論のときの付加的なルールとして単相性制限というのがあり、それを無効にするためのオプションがこのおまじないみたい。それにしても、単相性制限と (Stream s m Char) のインスタンスがないというエラーの関係はさっぱりわかりません。

単相性制限のことはいったん忘れて、パーサーの型を明示することに挑戦します。Parsec2 であれば GenParser Char st [String] なのですが、Parsec3 のパーサーの型は RWH には説明がありません。 NoMonomorphismRestriction を指定すればコンパイルに通ることはわかっているので、ずるをして GHC に型を教えてもらいます。

*Main GOA> :t parser
parser :: (Stream s m Char) => ParsecT s u m [Char]

おや、こんなところに Stream が。確かに、この型クラスのインスタンスが決まらないとパーサーの型が決まらなそうだけど、どうして単相性制限を使わないことにすると型推論が通ってしまうのだろう？

単相性制限のことはもう一度忘れて、GHC が教えてくれた型を明示してコンパイルしなおしてみます。

parser :: (Stream s m Char) => ParsecT s u m [Char]
parser = (++) <$> string "HT" <*> (string "TP" <|> string "ML")

結果

Non type-variable argument in the constraint: Stream s m Char
    (Use -XFlexibleContexts to permit this)
    In the type signature for `parser':
      parser :: (Stream s m Char) => ParsecT s () m [Char]

制約に型変数じゃないものがあるとな。しかも、回避したければやっぱりおまじないを唱えろと。

Parsec3 におけるパーサーの型

おまじないはいやなので、 ParsecT が何ものかを調べてきっちりナシを通すことにします。まずは Hackage のドキュメントを眺めます。すると次のことがわかりました。

• パーサーの型は ParsecT で、これはモナド変換子である。
• 厳密な型シグネチャは ParsecT s u m a
  • s は抽象化された入力の型。この抽象化された入力をストリームという。
  • u はパース時に好きな状態を格納しておく容器の型。
  • m はモナド変換子にとって基盤となるモナド。
  • a は出力の型

さらに、Stream というストリームを用立てるための型クラスがあって、そのインスタンスを作ることでパーサーへの入力の型が決まるようです。Stream のインスタンスになるには、入力の型（String とか）と、それを読み込んでいくときの単位の型（Char とか）、入力から 1単位だけ読み出して残りと組にして返す関数が必要です（実際には得られる組を Maybe でくるんだものをさらに基盤となるモナドでくるむので、そのモナドも与えます）。

ようやく見えてきました。parserの型、つまり文字列から文字列を探して返すパーサーの型は、 Monad m => ParsecT String u m String です。

import Control.Applicative hiding ((<|>))
import Text.Parsec

parser :: Monad m => ParsecT String u m String
parser = (++) <$> string "HT" <*> (string "TP" <|> string "ML")

結果

*Main GOA> parseTest parser "HTTP"
"HTTP"

もちろん必要なら u や m に具体的な何かを指定できます。何も例が思いつきませんが、いろいろ検索してみたら、ユーザーステートを配列代わりにして brainfuck を作り、処理結果を IO に直接吐き出すという使い方が……。

Haskell: ParsecのParsecによるBrainfuck（SnowClust）
http://inviernostring.blog106.fc2.com/blog-entry-32.html

ところで Parsec3 のパーサーの型は、brainfuck を作ったりするのでなければ、Parser String という具合にお手軽に指定できるようです（ Text.Parsec.String が必要）。

import Control.Applicative hiding ((<|>))
import Text.Parsec
import Text.Parsec.String

parser :: Parser String
parser = (++) <$> string "HT" <*> (string "TP" <|> string "ML")

これは、こういう定義が Parsec に用意されているからです。

type Parsec s u = ParsecT s u Identity

type Parser = Parsec String ()

つまり Parser という型変数を使うということは、入力としては String が、ユーザーステートとしては () が、基盤となるモナドとしては Identity が使われているということですね。

結局、単相性制限と最初のエラーの関係は？

もやもや中。