haskell - 应用解析相对于单子(monad)解析有什么好处？

Question

似乎有一个共识，您应该使用 Parsec 作为应用程序而不是 monad。应用解析相对于单子(monad)解析有什么好处？

• 风格
• 性能
• 抽象

单子(monad)解析结束了吗？

Answer 1

一元解析和应用解析之间的主要区别在于顺序组合的处理方式。对于应用解析器，我们使用 (<*>) ，而对于 monad，我们使用 (>>=) .

(<*>) :: Parser (a -> b) -> Parser a -> Parser b
(>>=) :: Parser a -> (a -> Parser b) -> Parser b

一元方法更加灵活，因为它允许第二部分的语法依赖于第一部分的结果，但我们在实践中很少需要这种额外的灵 active 。

您可能认为拥有一些额外的灵 active 不会有什么坏处，但实际上它可能会造成坏处。它阻止我们在不运行解析器的情况下对其进行有用的静态分析。例如，假设我们想知道解析器是否可以匹配空字符串，以及匹配中可能的第一个字符是什么。我们想要函数

empty :: Parser a -> Bool
first :: Parser a -> Set Char

使用应用解析器，我们可以轻松回答这个问题。 (我在这里有点作弊。假设我们有一个与候选解析器“语言”中的 (<*>) 和 (>>=) 相对应的数据构造函数)。

empty (f <*> x) = empty f && empty x
first (f <*> x) | empty f   = first f `union` first x
                | otherwise = first f

但是，使用一元解析器，在不知道输入的情况下，我们不知道第二部分的语法是什么。

empty (x >>= f) = empty x && empty (f ???)
first (x >>= f) | empty x   = first x `union` first (f ???)
                | otherwise = first x

通过允许更多，我们能够推理得更少。这类似于动态和静态类型系统之间的选择。

但这有什么意义呢？我们可以用这些额外的静态知识做什么？好吧，我们可以使用它来避免 LL(1) 解析中的回溯，方法是将下一个字符与 first 进行比较。每个备选方案的集合。我们还可以通过检查 first 是否静态地确定这是否不明确。两个备选方案重叠。

另一个例子是它可以用于错误恢复，如论文Deterministic, Error-Correcting Combinator Parsers所示作者:S. Doaitse Swierstra 和 Luc Duponcheel。

但是，通常情况下，您正在使用的解析库的作者已经做出了应用解析和单子(monad)解析之间的选择。当像 Parsec 这样的库公开两个接口(interface)时，选择使用哪一个纯粹是一种风格。在某些情况下，应用代码比单子(monad)代码更容易阅读，有时恰恰相反。