如何从 `a -> Parser b` 到 `Parser (a -> b)`？

Question

我正在尝试更新使用Text.Parsec.Expr的秒差距解析器。我正在尝试（这可能是不明智的，但看起来应该是实用的）将 DSL 验证的一部分构建到解析器中。但我很难让它与类型一起工作，它的主体需要是一个生成函数的解析器buildExpressionParserOperator。

\n

data Location = Location { owners :: PartySet, source :: SourcePos } deriving (Eq, Ord, Show)\ntype Located = (,) Location\ntype Parser = Parsec String (Map Variable PartySet)\n\n-- Pair a parsed thing with it\'s position in the source file\npositioned :: Parser a -> Parser (SourcePos, a)\npositioned p = do source <- getPosition\n                  (source,) <$> p\n\nchooseOf :: (TokenParser st -> t -> Parsec.Parser a) -> [t] -> Parser (SourcePos, a)\nchooseOf cls subcls = choice $ [positioned $ cls tokenizer sc | sc <- subcls]\n\n-- Define parser for Algebra\nalgebraParser :: Parser (Located (Algebra Located))\nalgebraParser = buildExpressionParser ops terms\n\nterms = parens tokenizer algebraParser <|> litParser <|> varParser\n\n-- Parse a Literal Bit (0 or 1)\nlitParser = do (source, b) <- (const (Bit True) <$$> chooseOf reserved trueNames)\n                               <|> (const (Bit False) <$$> chooseOf reserved falseNames)\n               let loc = Location{source, owners=top}\n               return (loc, Literal (loc, b))\n\n-- Parse a variable as they appear in algebra terms\nvarParser = do (loc, var) <- boundVariable\n               return (loc, Var (loc, var))\n\n-- Step 1 for building the Operator objects\nbiOpParser :: (Located (Algebra Located) -> Located (Algebra Located) -> Algebra Located)\n              -> SourcePos\n              -> (Located (Algebra Located), Located (Algebra Located))\n              -> Parser (Located (Algebra Located))\nbiOpParser constructor source (alg1@(Location{owners=o1}, _), alg2@(Location{owners=o2}, _)) =\n  do let mowners = o1 `intersect` o2\n     maybe (parserFail "Can\'t compute binary operator. Nobody owns both arguments")\n           (\\owners -> return (Location{source, owners}, constructor alg1 alg2))\n           mowners\n\n-- Step 2, broken out for the XOR case.\nxorParser :: Parser (Located (Algebra Located) -> Located (Algebra Located) -> Located (Algebra Located))\nxorParser = do (source, _) <- chooseOf reservedOp xorNames\n               curry <$> sequence (biOpParser Xor source)\nops :: OperatorTable String (Map Variable PartySet) Identity (Located (Algebra Located))\nops = [ [Prefix $ do (source, _) <- chooseOf reservedOp notNames\n                     return \\alg@(loc, _) -> (loc{source}, Not alg)]\n       ,[Infix xorParser AssocLeft]\n       -- Step 3; the AND case has step 2 inlined.\n       ,[Infix (do (source, _) <- chooseOf reservedOp andNames\n                   curry <$> sequence (biOpParser And source)) AssocLeft] ]\n

\n

如果有帮助的话，我可以添加更多代码；或者我可以尝试将其简化为更纯粹的情况。

\n

问题出在内部algebraParser；我想使用buildExpressionParser，这需要一个 s 表Operator。
\n问题的核心在于parserFail "Can\'t XOR. Nobody owns both arguments"内部biOpParser。
\n操作项（如XOR）可能有效也可能无效，具体取决于其参数的“类型”（所有权）。我正在尝试使用解析器单子的“用户状态”来存储所有权，并且（相应地）我希望违规行为显示为解析器错误。这意味着测试需要编写在 Parser monad 内部，以便我可以使用parserFail，但这与生成“op函数”的需要相冲突。

\n

上面代码显示的实际错误是sequence (biOpParser Xor source)内部的xorParser：

\n

No instance for (\n  Traversable (\n    (->) (Located (Algebra Located), Located (Algebra Located))\n  )\n) arising from a use of \xe2\x80\x98sequence\xe2\x80\x99\n

\n

我知道反转任意对嵌套单子是不可能/明智的；据我所知也没有帮助，对吗？

\n

有一个简单的解决办法吗？我的方法是否有可能有效的合理改变？我是否误用或误解了其他一些基本的东西？

\n

Answer 1

对你的问题的两条评论已经给了你答案：你不能编写类型为 的函数(a -> Parser b) -> Parser (a -> b)。要了解原因，请考虑该类型的含义。我为您提供了一种方法，给定 type 的值a，解析另一个 type 的值b。由此，您必须给我返回一个解析器，该解析器生成从a到 的函数b。重要的是，请注意以下两件事：

1. 结果，您返回给我的解析器没有a可查看的值，因此您无法调用我传递给您的函数。
2. 您的解析器返回的函数必须不进行解析。这是一个简单的 type 函数a -> b：任何地方都没有Parser，所以它只是一个无聊的纯函数。你不能让该函数的实现是“首先，调用a -> Parser b我给出的函数，然后解析 a b，然后返回它”，因为它不允许解析任何内容。

从这两点来看，我希望更清楚地表明这个签名不可能有任何功能。