トップ > Haskell > 「プログラミング Haskell」 読書メモ 第8章 関数型パーサー(1)

「プログラミング Haskell」 読書メモ 第8章 関数型パーサー(1)

Haskell

プログラミング Haskell 第8章 関数型パーサー

8.2 パーサーの型

import Char
import Monad

newtype Parser a =  P (String -> [(a,String)])

instance Monad Parser where
  return v      =  P (\inp -> [(v,inp)])
  p >>= f       =  P (\inp -> case parse p inp of
                                 []        -> []
                                 [(v,out)] -> parse (f v) out)

instance MonadPlus Parser where
  mzero         =  P (\inp -> [])
  -- p のパース適用に失敗したときは q のパースを適用する
  p `mplus` q   =  P (\inp -> case parse p inp of
                                 []        -> parse q inp
                                 [(v,out)] -> [(v,out)])

8.3 基本的なパーサー

failure :: Parser a
failure = mzero

item :: Parser Char
item = P (\inp -> case inp of
                     []     -> []
                     (x:xs) -> [(x,xs)])

parse            :: Parser a -> String -> [(a,String)]
parse (P p) inp  =  p inp

parse (return 1) "abc" --=> [(1,"abc")]
parse failure "abc"    --=> []
parse item "abc"       --=> [('a',"bc")]

8.5 選択
p のパース適用に失敗したときは q のパースを適用する

infixr 5 +++

(+++)   :: Parser a -> Parser a -> Parser a
p +++ q =  p `mplus` q

parse (item +++ item) "abc"          --=> [('a',"bc")]
parse (item +++ return 'd') "abc"    --=> [('a',"bc")]
parse (failure +++ return 'd') "abc" --=> [('d',"abc")]

「p のパース適用に失敗したときは q のパースを適用する」関数を"abc"に適用させる。手続き型言語との違いが特徴的だ。

8.6 パーサーの部品

sat :: (Char -> Bool) -> Parser Char
sat p =  do x <- item
            if p x then return x else failure

digit :: Parser Char
digit = sat isDigit

parse digit "123"  --=> [('1',"23")]
parse digit "abc"  --=> []

lower :: Parser Char
lower =  sat isLower

parse lower "abc" --=> [('a',"bc")]
parse lower "aBC" --=> [('a',"BC")]

upper :: Parser Char
upper =  sat isUpper

letter :: Parser Char
letter =  sat isAlpha

parse letter "abc" --=> [('a',"bc")]
parse letter "Abc" --=> [('A',"bc")]
parse letter "1bc" --=> []

alphanum :: Parser Char
alphanum =  sat isAlphaNum

char   :: Char -> Parser Char
char x = sat (== x)

parse (char ' ') " bc" --=> [(' ',"bc")]
parse (char 'x') " bc" --=> []