モナディックなパーザーコンビネータ作ってみた

タイトル通りで作ってみたました. もともと研究で違うことやってたはずなのに目的を見失ってなんか面白そうだしこれならゼミで話しても怒られなさそうという考えからこの頃ずっと勉強してた.

OCamlで実装しようかHaskellで実装しようか迷っててどっちでも良かったんだけど最終的にはHaskellで書いた. 最初はOCamlの勉強も少ししてて、とにかく本を買いたくなかったので以下のページを読んでた.

けど素直にHaskellでやったほうが楽そうという気持ちになり途中からHaskellに切り替えた. Haskellの文法は雰囲気がわかる程度だったのでなんとかなるだろうと思い特に何もしなかった. モナドは「モナドは単なる自己関手の圏におけるモノイド対象だよ。何か問題でも?」という感じだったので以下のページを読んでだ.

パーザーコンビネータググるといろんな人が実装しててるのでそれを参考にするといいかもしれない. こんなふうにParserの型が決まった時点で考えることはあんまりなくて型すごいって思いながら実装しいくとできたし型すごい.

type Result = Either String
type Parser v = StateT String Result v

PEGパーザにした気でいるんですがもしかしたらこれではいけないかもしれないので間違っていたらスマンという感じです.

import Control.Monad.State
import GHC.Base((<|>))
import Data.Char

type Result = Either String

type Parser v = StateT String Result v

runParser = runStateT

look :: Parser Char
look = do
  x:_ <- get
  return x

item :: Parser Char
item = do
  x:xs <- get
  put xs
  return x

satisfy :: (Char -> Bool) -> Parser Char
satisfy f = do
  a <- item
  if f a then return a else mzero

unsatisfy :: (Char -> Bool) -> Parser Char
unsatisfy f = satisfy (not . f)

cjoin :: Parser a -> Parser a -> Parser [a]
cjoin p1 p2 = do
  a <- p1
  b <- p2
  return [a, b]

select :: Parser a -> Parser a -> Parser a
select = (<|>)

many :: Parser a -> Parser [a]
many f = many1 f <|> return []

many1 :: Parser a -> Parser [a]
many1 f = do
  a <- f
  b <- many f
  return $ a:b

例えばExpr <- Number + Numberを受理するためのは以下のように書くとちゃんと計算結果が返ってくる.

number :: Parser Integer
number = do
  n <- many1 digit
  return $ read n
  where digit = satisfy isDigit

expr :: Parser Integer
expr = do
  a <- number
  op <- token (=='+') >> return (+)
  b <- number
  return $ op a b

main :: IO ()
main = print $ runStateT expr2 "1+2;" -- => Right (3,";")

4則演算バージョンがあるのでぜひ

sample.hs · GitHub

参考

感想

エンドレスモナドチュートリアルが終わって新学期が来た感じ