parsing - 具有变形的 Haskell monadic 解析器

Question

我的问题是如何将递归的 F 代数风格的递归类型定义与单子(monad)/应用风格的解析器结合起来，以适应现实的编程语言。
我刚开始使用 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) )，它应该解析左侧和右侧的表达式。
但是，(monadic/applicative)解析器不是这样工作的:

他们首先尝试解析左侧表达式

+ ,

和右 watch 达式

我看到的一种解决方案是更改 Plus a a 的类型定义。至 Plus Integer a ，这样它就反射(reflect)了解析过程，但这似乎不是最好的途径。
欢迎任何建议(或阅读指导)!

Answer 1

如果你需要一个单子(monad)解析器，你需要一个单子(monad)在你的展开:

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

然后你可以写一些东西来解析 ExprF 的一个级别。像这样:

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 ，当然，但是编译器可以为您编写这些，并且它们本身不是递归的。