适用性解析相比单子解析有哪些优势？

Question

适用性解析相比单子解析有哪些优势？

haskellmonadsparsecapplicative

75

似乎有共识认为应该把Parsec作为可应用的而不是单子的。在应用解析和单子解析之间，应用解析有什么好处呢？

风格
性能
抽象化

单子解析已经过时了吗？

- gawi

5个回答

15

如果解析器是纯应用的，可以在运行之前分析其结构并进行“优化”。如果解析器是单子类型的，则基本上它是一个图灵完备程序，而对其执行几乎任何有趣的分析都等价于解决停机问题（即不可能）。

哦，对了，还有一种风格上的区别...

- MathematicalOrchid

1

Applicative和Monad之间的区别与图灵完备性无关。在Haskell中，优化Monad实例的相对困难仅源于将(>>=)单独暴露在类型类中的历史错误，这使得实例无法提供更优化的操作符实现，例如ap。Applicative类避免了这个错误，并公开了<*>（相当于ap）的使用。 - Pi Delport

@PietDelport，我认为问题在于单子解析器的基础表示通常不适合优化的Applicative实例，而Applicative解析器通常不支持>>=。 - dfeuer

4

完全与图灵完备性有关。>>= 接收左侧解析器的结果并将其传递给右侧解析器，因此使得生成的解析器不可进行静态分析，因为现在解析器本身是图灵完备的。 <*> 和 <$> 不检查参数，因此，虽然解析器本身的输出是图灵完备的，因为您可以将任何东西放在 <$> 的左侧，但解析方面本身是受限的和静态可分析的。 - semicolon

14

我能看出使用应用型解析器比单子型解析器更好的主要原因是，在任何情况下，喜欢应用程序代码胜过单子代码的主要原因是：应用程序较弱，因此使用起来更简单。

这是一种更普遍的工程法则的实例：使用最简单的工具完成工作。不要在只需要手推车时使用叉车。不要在切割优惠券时使用台锯。不要在可以使用纯代码时使用IO。保持简单。

但有时，您需要Monad的额外功能。如果您需要根据已计算的内容更改计算的进程，则可以确定这一点。在解析术语中，这意味着基于迄今为止已解析的内容确定如何解析接下来的内容；换句话说，您可以以这种方式构造上下文相关的语法。

- Tom Crockett

3

不，“使用最简单的工具”可能看起来是一个不错的经验法则，但实际上并不是。例如，我们使用电脑写信，然而相对于一张纸而言，电脑就像是一把台锯和一把剪刀之间的区别。 - Valentin Golev

我的意思是，每个选择总有利弊，但仅仅出于简单而做出选择是一个糟糕的基础。特别是当你在决定是否使用Haskell时。:D - Valentin Golev

6

没错，更好的说法应该是，“最合适的工具是在保持尽可能简洁的同时最大限度地提高效率。”我的描述缺少了一个关键点：你需要一个足够强大的工具，不仅可以完成任务，而且可以让任务变得尽可能轻松。但同时，你不希望工具有很多与手头任务无关的花里胡哨的功能，因为这些功能很可能会增加其操作复杂性而没有任何好处。 - Tom Crockett

4

使用Parsec时，使用Applicative的好处仅在于风格上。而Monad更强大——您可以实现上下文敏感的解析器。

如果仅以应用程序方式使用Doaitse Swierstra的UU解析器，则其效率更高。

- stephen tetley

4

我对你的评论很好奇。这是一种语言，字母表是Haskell中的字符串，这种语言的单词由相同字母组成。使用单子解析器非常容易： option [] (anyToken >>= many . exactToken)（这里的anyToken和exactToken实际上不是Parsec库的一部分，但可能应该是; 如果您不确定它们的作用，请问我）。相应的应用解析器会是什么样子？ - Daniel Wagner

2

@stephen，你能给一个关于上下文敏感解析器的参考吗？我很好奇单子和应用解析器的确切能力是什么。 - sdcvvc

1

@sdcvvc：这篇论文讨论了箭头解析器与单子解析器的相对能力，并指出单子解析器可以解析上下文敏感语法，而箭头则不能。我认为应用解析器的能力严格低于箭头解析器。 - Tom Crockett

3

这篇文章（和评论）解释了应用解析器允许解析所有递归可枚举语言的原理： http://byorgey.wordpress.com/2012/01/05/parsing-context-sensitive-languages-with-applicative/ - Blaisorblade

@DanielWagner，五年后才回复你：你可以懒惰地枚举所有只包含一个字符的字符串并应用asum。如果解析器的<|>足够懒惰，我相信这将以非常低效的方式为您提供所需的语法。当然，并非所有解析器都有懒惰的<|>。regex-applicative肯定没有；我不知道更传统的解析器组合库是否有。 - dfeuer

显示剩余2条评论

3

单子（Monads）是比应用函子（Applicatives）更丰富的抽象。你可以这样写：

instance (Monad m) => Applicative m where
  pure  = return
  (<*>) = ap

但是没有编写的方法

instance (Applicative a) => Monad a where
  return = pure
  (>>=) = ???

所以，这实际上是一种风格问题。我想如果你使用return和ap，那么与使用pure和<*>相比，应该没有性能损失。因为Applicative是比Monad更严格的接口，这意味着<*>有时可以比ap更高效地优化。(但是通过巧妙的GHC重写规则，通常可以实现相同的优化。)

Monadic parsing过时了吗？

由于Monad是Applicative的子集，我认为applicative parsing是monadic parsing的子集。

- Dan Burton

你的意思是说单子（Monads）是应用函子（Applicatives）的超集吗？ - Guildenstern

2

@Guildenstern 单子操作是应用操作的超集。但换句话说：具有“Monad”实例的类型是具有“Applicative”实例的类型的子集。当谈论“单子”和“应用程序”时，通常指的是类型，而不是操作。 - Dan Burton

2

如果使用 return 和 ap，就不应该比使用 pure 和 <*> 有任何性能损失。但据我所知并非如此。在许多情况下（解析器只是其中之一），<*> 的性能要优于 ap。 - semicolon

@semicolon 你说得完全正确；我已经相应地更新了我的答案。 - Dan Burton

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hammar · Accepted Answer

单子解析和应用解析的主要区别在于如何处理顺序组合。对于应用解析器，我们使用 (<*>)，而对于单子解析器，我们使用(>>=)。

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

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

你可能认为拥有一些额外的灵活性不会有任何问题，但实际上会有影响。它阻止了我们在运行解析器之前进行有用的静态分析。例如，假设我们想知道解析器是否能够匹配空字符串以及可能的匹配的第一个字符是什么。我们需要函数

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集是否重叠，从静态上确定该语法是否存在歧义。另一个例子是它可用于误差恢复，正如S. Doaitse Swierstra和Luc Duponcheel在论文确定性、纠错组合解析器中所示。通常，然而，应用型解析和单子解析之间的选择已经由您使用的解析库的作者做出。当像Parsec这样的库公开了这两种接口时，使用哪种接口的选择纯粹是基于个人风格的。在某些情况下，应用代码比单子代码更易读，而有时则相反。