プログラミングHaskellを読む(8)
久々の更新です。
この章はかなりきついです。以下を理解するまでに3回ぐらい投げてます。
第8章 関数型パーサー
基本
実際に動かすことができた所のソースコードを載せます。
import Char type Parser a = String -> [(a, String)] -- 入力をそのまま出力にするパーサを生成する関数 -- テキストではreturn ret :: a -> Parser a ret v = \inp -> [(v, inp)] -- 必ず失敗するパーサ failure :: Parser a failure = \inp -> [] -- 入力が空なら失敗。 -- そうでなければ最初の文字を取り、そのまま出力とする文字列パーサ。 item :: Parser Char item = \inp -> case inp of [] -> [] (x : xs) -> [(x, xs)] -- パース関数 -- パーサと文字列を受け取り、パーサを適用する parse :: Parser a -> String -> [(a, String)] parse p inp = p inp -- 例 ex1 = parse (ret 1) "abc" ex2 = parse failure "abc" ex3 = parse item "abc" -- パーサの連結。">>="は組み込みなので、soとする。 so :: Parser a -> (a -> Parser b) -> Parser b p `so` f = \inp -> case parse p inp of [] -> [] -- 失敗 [(v, out)] -> parse (f v) out -- 成功 -- 例 ex4 = item `so` \v -> ret v ex5 = item `so` \v1 -> item `so` \v2 -> item `so` \v3 -> ret (v1 : v2 : [v3]) {- doはモナドで型定義しないと使えないらしい p :: Parser (Char, Char) p = do x <- item item y <- item return (x, y) -} -- 選択。+++は組み込みではないので定義できる。 (+++) :: Parser a -> Parser a -> Parser a p +++ q = \inp -> case parse p inp of [] -> parse q inp [(v, out)] -> [(v, out)]
ここまでで、基本的な部分は終了です。しかし、正直よく分からりません。そこで例を考えてみました。
例えば、ある関数numが以下のような動作をするとします。
- "num 入力文字列"に対し
- 入力から先頭1文字を取り出し、数値に変える。
- 入力文字列が空の時、失敗。先頭が数値でないときも失敗。
- 失敗の時は空リスト[]を返す。
- 成功なら[(変換したInt型の数値、残り)]」。
このnum関数がParser型*1です。実際に書いてみれば
num :: Parser Int num = \inp -> case inp of [] -> [] (x : xs) -> if isDigit x then [(digitToInt x, xs)] else []
といった感じです。ret, failure, itemに似た部分がそこかしこに見受けられますね。
ここで、数値だけの文字列について、その合計を出すsum_パーサを作ってみます。数値以外が文字列に含まれる場合は、そこまでの和とします。いきなり作るのは無理*2なので、まず2個足す場合のsum2を作ってみます。
sum2 :: Parser Int sum2 = \inp -> case num inp of [] -> [(0, inp)] [(v1, inp1)] -> case num inp1 of [] -> [(v1, inp1)] [(v2, inp2)] -> [(v1+v2, inp2)]
なんかso関数*3っぽいものが見えてきました。この要領で再帰させればsum_関数が作れそうです。
sum_ :: Parser Int sum_ = \inp -> case num inp of [] -> [(0, inp)] [(v1, inp1)] -> case sum_ inp1 of [] -> [(0, inp1)] [(v2, inp2)] -> [(v1+v2, inp2)]
sum2の2個目のnumをsum_にしただけです。
とりあえずコレがパーサの本質になるかと思います。これを前述のret v, failure, item, parse, so, +++で表現してみます。
num' :: Parser Int num' = item `so` \v -> if isDigit v then ret (digitToInt v) else ret 0 +++ ret 0 sum2' :: Parser Int sum2' = num' `so` \v1 -> num' `so` \v2 -> ret (v1+v2) sum_' :: Parser Int sum_' = num' `so` \v1 -> sum_' `so` \v2 -> ret (v1+v2)
sum2'はOKなのですが、sum_'は思うように動きませんでした。何故…?
とはいえ、まぁ大体こんな感じじゃないかなと思ってます。これ以降はdoが使えないと面白く無いのでとりあえずスキップすることにし*4、10章が終わったらまた戻ってくることにします。