底层Parsec Monad

Question

我使用的许多Parsec组合器都属于一种类型，例如：

foo :: CharParser st Foo

CharParser被定义为这里：

type CharParser st = GenParser Char st

因此，CharParser是一个涉及GenParser的类型同义词，它本身将这里定义为：

type GenParser tok st = Parsec [tok] st

然后，GenParser是另一种类型的同义词，使用Parsec指定，将这里定义为：

type Parsec s u = ParsecT s u Identity

因此，Parsec是ParsecT的部分应用程序，它本身列出的这里类型如下：

data ParsecT s u m a

连同以下几个字：

"ParsecT s u m是一个具有流类型s、用户状态类型u、底层monad m和返回类型a的解析器。“

什么是最底层的单元组？特别是，当我使用CharParser解析器时，它是什么？我看不出它在堆栈里的位置。在Haskell中的一元分析中使用list monad从一个不明确的解析器返回多个成功的分析有关系吗？

Answer 1

GenParser是用Parsec而不是ParsecT来定义的。Parsec依次被定义为

type Parsec s u = ParsecT s u Identity

因此，答案是，当使用CharParser时，底层的monad就是Identity monad。

Answer 2

在您的例子中，底层的monad是Identity。但是，ParsecT与大多数单台变压器不同，因为它是Monad类的一个实例，即使类型参数m不是。如果您查看源代码，您将注意到实例声明中缺少"(Monad m) =>“。

然后你会问自己，“如果我有一个非平凡的单栈，它会在哪里使用？”

这个问题有三个答案：

1. 它用于将下一个令牌从流中uncons出来： 类(Monad ) => Stream的m t=s -> t，其中uncon :：s -> m(可能(t，s)) 注意，uncons接受一个s (令牌的流t)，并返回它的结果封装在您的monad中。这允许一个人在获得下一个令牌的过程中或甚至在获得下一个令牌的过程中做有趣的事情。
2. 它用于每个解析器的结果输出。这意味着您可以创建不接触输入但在底层单体中执行操作的解析器，并使用组合器将它们绑定到常规解析器。换句话说，lift (x :: m a) :: ParsecT s u m a。
3. 最后，RunParsecT和朋友的最终结果(直到建立到m被Identity替换的程度)返回包装在这个单子中的结果。

这个单子和Haskell中的一元分析的那个没有任何关系。在本例中，Hutton和Meijer指的是ParsecT本身的monad实例。在Parsec-3.0.0及更高版本中，ParsecT已成为一个具有底层monad的单一转换器，这与论文无关。

然而，我认为你正在寻找的是可能的结果的清单。在Hutton和Meijer中，解析器返回所有可能结果的列表，而Parsec只返回一个结果。我认为您正在查看结果中的m，并且自己认为结果列表肯定隐藏在某个地方。事实并非如此。

Parsec出于效率的考虑，选择了Hutton和Meijer的结果列表中的第一个匹配结果。这就让我们扔掉Hutton和Meijer的列表中未使用的结果，以及令牌流的前端，因为我们从未回溯过。在parsec中，给定合并的解析器a <|> b，如果a消耗了任何输入b，则永远不会计算b。方法是try，如果a失败，它会将状态重置回原来的位置，然后计算b。

您在评论中询问这是使用Maybe还是Either完成的。答案是“几乎，但不完全”。如果您查看低级别的run*函数，您会发现它们返回一个代数类型，它告诉天气输入被消耗，然后第二个函数给出结果或错误消息。这些类型有点像Either，但即使它们也不是直接使用的。相反，我将向您介绍安托万的岗位，后者解释了这是如何工作的，以及为什么是这样做的。