11

我使用的许多 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 suma 是一个具有流类型 s、用户状态类型 u、底层 monad m 和返回类型 a 的解析器。”

什么是底层的单子？特别是，当我使用CharParser解析器时它是什么？我看不到它在堆栈中的插入位置。在 Haskell 的 Monadic Parsing 中使用 list monad从一个模棱两可的解析器返回多个成功的解析是否有关系？

4

2 回答 2

9

在您的情况下，基础单子是Identity. 然而 ParsecT 与大多数 monad 转换器的不同之处在于它是Monad类的一个实例，即使类型参数m不是。如果您查看源代码，您会注意到(Monad m) =>实例声明中缺少“”。

那么你问自己，“如果我有一个非平凡的 monad 堆栈，它将在哪里使用？”

这个问题有三个答案：

  1. 它用于uncons流中的下一个标记：

    class (Monad m) => Stream s m t | s -> t where
    uncons :: s -> m (Maybe (t,s))

    请注意，它uncons接受一个s（令牌流t）并返回其包装在您的 monad 中的结果。这允许人们在获得下一个令牌的过程中甚至在获得下一个令牌的过程中做有趣的事情。

  2. 它用于每个解析器的结果输出。这意味着您可以创建不接触输入但在底层 monad 中执行操作的解析器，并使用组合器将它们绑定到常规解析器。换句话说，lift (x :: m a) :: ParsecT s u m a.

  3. m最后，RunParsecT 和朋友的最终结果（直到你建立到被 替换的地步Identity）返回包装在这个 monad 中的结果。

这个单子与Haskell 中 Monadic Parsing 中的单子没有关系。在这种情况下，Hutton 和 Meijer 指的是 ParsecT 本身的 monad 实例。在 Parsec-3.0.0 及更高版本中 ParsecT 已成为具有底层 monad 的 monad 转换器这一事实与本文无关。

但是，我认为您正在寻找的是可能结果列表的去向。在 Hutton 和 Meijer 中，解析器返回所有可能结果的列表，而 Parsec 固执地只返回一个。我认为您正在查看m结果，并认为结果列表必须隐藏在某个地方。它不是。

Parsec 出于效率的原因，选择更喜欢 Hutton 和 Meijer 的结果列表中的第一个匹配结果。这让它在 Hutton 和 Meijer 列表的尾部以及令牌流的前面丢弃未使用的结果，因为我们从不回溯。在 parsec 中，给定组合 parser a <|> b，如果使用a任何输入，b则永远不会被评估。解决这个问题的方法是try将状态重置回如果a失败然后评估的位置b。

您在评论中询问这是否是使用Maybeor完成的Either。答案是“几乎但不完全”。如果您查看低级别run*函数，您会看到它们返回一个代数类型，它告诉天气输入已被消耗，然后是第二个给出结果或错误消息。这些类型的工作方式有点像Either，但即使它们也不直接使用。与其进一步扩展这一点，我将向您推荐 Antoine Latter的帖子，该帖子解释了它是如何工作的以及为什么这样做。

于 2013-04-26T22:16:02.943 回答
6

GenParser 是根据 Parsec 而不是 ParsecT 定义的。Parsec 又被定义为

type Parsec s u = ParsecT s u Identity

所以答案是，当使用 CharParser 时，底层 monad 是 Identity monad。

于 2011-11-08T17:12:35.720 回答