I was looking for a simple formulation of breadth first parser combinators. I found out it is pretty easy to invent them yourself if you use a coinductive data type:
data Parser a = Parser
{ now :: [a]
, next :: Char -> Parser a
} deriving Functor
instance Applicative Parser where
pure x = Parser [x] (const empty)
(<*>) = ap
instance Monad Parser where
Parser now next >>= k =
asum (map k now) <|> Parser [] (\c -> next c >>= k)
instance Alternative Parser where
empty = Parser [] (const empty)
Parser now1 next1 <|> Parser now2 next2 =
Parser (now1 ++ now2) (\c -> next1 c <|> next2 c)
char :: Char -> Parser ()
char c = Parser [] (\c' -> guard (c == c'))
parse :: Parser a -> String -> [a]
parse (Parser now _) [] = now
parse (Parser _ next) (x:xs) = parse (next x) xs
Some observations and questions:
- With the normal recursive descent approach one tactic to speed up the parser is to commit to the first successful branch. Could we do the same or something similar using corecursive parsers?
- The coinductive parser data type itself looks a bit like the list data type:
now
corresponds toNil
andnext
corresponds toCons
. Is there a connection there? Could/should the data type be changed to match the list type more closely?