プログラミング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章が終わったらまた戻ってくることにします。

*1:正確には"Parser Int"型

*2:私の脳のスペック的に

*3:>>=演算子

*4:一応読みはしましたが

第8章 関数型パーサー

基本

第8章関数型パーサー