类似 Foldl 的 Parsec 运算符

Question

假设我有一个这样的函数：

once :: (a, b) -> Parser (a, b)

现在，我想重复应用这个解析器（有点像使用 >>=）并在下一次迭代中使用它的最后输出来提供它。

使用类似

的东西

sequence :: (a, b) -> Parser (a, b)
sequence inp = once inp >>= sequence

为第一个解析器指定初始值是行不通的，因为它会继续下去，直到不可避免地失败。相反，我希望它在失败时停止（有点像 many）。

尝试使用 try 修复它会使计算过于复杂（在每次迭代中添加尝试）。

sequence :: (a, b) -> Parser (a, b)
sequence inp = try (once inp >>= sequence) <|> pure inp

换句话说，我正在寻找一个类似于 foldl 上的解析器的函数，它会在下一个解析器失败时停止。

Answer 1

如果您的 once 解析器在不消耗输入的情况下立即失败，则您不需要 try。作为一个具体的例子，考虑一个相当愚蠢的 once 解析器，它使用一对定界符来解析下一对定界符：

once :: (Char, Char) -> Parser (Char, Char)
once (c1, c2) = (,) <$ char c1 <*> anyChar <*> anyChar <* char c2

您可以使用以下方法解析嵌套序列：

onces :: (Char, Char) -> Parser (Char, Char)
onces inp = (once inp >>= onces) <|> pure inp

效果很好：

> parseTest (onces ('(',')')) "([])[{}]{xy}xabyDONE"
('a','b')

如果您的 once 在解析输入后可能会失败，则您只需要 try。例如，如果不尝试，以下内容将无法解析：

> parseTest (onces ('(',')')) "([])[not valid]"
parse error at (line 1, column 8):
unexpected "t"
expecting "]"

因为我们在发现not valid].

之前就开始解析开始分隔符[

（try，它 returns 正确的 ('[',']')。）

综上所述，我不知道您是如何得出使用 try 会使计算“过于复杂”的结论的。如果您只是根据读到的有关 try 可能效率低下的内容进行猜测，那么您就误解了。 try 如果以可能导致大量回溯的方式使用它，可能会导致问题。这在这里不是问题 - 最多，你回溯一个 once，所以不用担心。

Foldl-like operator for Parsec