Монадический синтаксический анализатор Haskell с анаморфизмами

Question

Моя проблема в том, как объединить рекурсивные определения рекурсивных типов в стиле F-алгебры с монадическими / аппликативными синтаксическими анализаторами таким образом, чтобы это можно было масштабировать до реалистичного языка программирования.

Я только начал с Expr определение ниже:

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

и я пытаюсь объединить его с парсером, который использует анаморфизмы:

      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 = ???

насколько я мог понять, в моем примере, psi должен либо анализировать только целое число, либо он должен решить, что строка является <expr> + <expr> а затем (рекурсивно вызывая fmap (ana psi)), он должен анализировать левую и правую части выражения.

Однако (монадические / аппликативные) парсеры так не работают:

• они сначала пытаются разобрать левое выражение,
• в +,
• и правое выражение

Одно из решений, которое я вижу, - это изменить определение типа для Plus a a к Plus Integer a, так что он отражает процесс синтаксического анализа, однако это не кажется лучшим способом.

Любые предложения (или направления чтения) приветствуются!

Answer 1

Если вам нужен монадический синтаксический анализатор, вам понадобится монада в вашем развертывании:

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

Затем вы можете написать что-то, что анализирует только один уровень, например:

      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))

Учитывая это, теперь у вас есть рекурсивный Expr парсер:

      parseExpr :: Parser Expr
parseExpr = anaM parseExprF Nothing

Вам понадобятся экземпляры Foldable а также Traversable для ExprFконечно, но компилятор может написать их за вас, и они сами по себе не рекурсивны.