Breadth-first corecursive parser combinators

Show and Tell
#1

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 to Nil and next corresponds to Cons. Is there a connection there? Could/should the data type be changed to match the list type more closely?
1 Like
#2

There could be one. But instead of just a list, the following paper used the stream processors of Fudgets fame:

I believe this is the associated package:

1 Like