Haskell monadic parser with anamorphisms

Question

My problem is how to combine the recursive, F-algebra-style recursive type definitions, with monadic/applicative-style parsers, in way that would scale to a realistic programming language.

I have just started with the Expr definition below:

data ExprF a = Plus a a |
              Val Integer deriving (Functor,Show)
data Rec f = In (f (Rec f)) 
type Expr = Rec ExprF

and I am trying to combine it with a parser which uses anamorphisms:

ana :: Functor f => (a -> f a) -> a -> Rec f
ana psi x = In $ fmap (ana psi) (psi x)

parser = ana psi
          where psi :: String -> ExprF String
                psi = ???

as far as I could understand, in my example, psi should either parse just an integer, or it should decide that the string is a <expr> + <expr> and then (by recursively calling fmap (ana psi)), it should parse the left-hand side and the right-hand side expressions.

However, (monadic/applicative) parsers don't work like that:

• they first attempt parsing the left-hand expression,
• the +,
• and the right-hand expression

One solution that I see, is to change the type definition for Plus a a to Plus Integer a, such that it reflects the parsing process, however this doesn't seem like the best avenue.

Any suggestions (or reading directions) would be welcome!

Answer 1

If you need a monadic parser, you need a monad in your unfold:

anaM :: (Traversable f, Monad m) => (a -> m (f a)) -> a -> m (Rec f)
anaM psiM x = In <$> (psiM x >>= traverse (anaM psiM))

Then you can write something that parses just one level of an ExprF like this:

parseNum :: Parser Integer
parseNum = -- ...

char :: Char -> Parser Char
char c = -- ...

parseExprF :: Maybe Integer -> Parser (ExprF (Maybe Integer))
parseExprF (Just n) = pure (Val n)
parseExprF Nothing = do
    n <- parseNum
    empty
        <|> (Plus (Just n) Nothing <$ char '+')
        <|> (pure (Val n))

Given that, you now have your recursive Expr parser:

parseExpr :: Parser Expr
parseExpr = anaM parseExprF Nothing

You will need to have instances of Foldable and Traversable for ExprF, of course, but the compiler can write these for you and they are not themselves recursive.