Haskell monadic 解析器与变形

Question

我的问题是如何将递归的、F 代数风格的递归类型定义与 monadic/applicative 风格的解析器结合起来，以适应现实的编程语言。

我刚刚开始使用以下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应该只解析一个整数，或者它应该决定字符串是 a<expr> + <expr>然后（通过递归调用fmap (ana psi)），它应该解析左侧和右侧的表达式.

但是，（monadic/applicative）解析器不是这样工作的：

• 他们首先尝试解析左边的表达式，
• 的+，
• 和右手表达

我看到的一种解决方案是更改 to 的类型定义，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))

然后你可以编写一些只解析一层的东西，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和Traversablefor的实例ExprF，但编译器可以为您编写这些实例，并且它们本身不是递归的。