parsing - 底层秒差距单子(monad)

Question

我使用的许多秒差距组合器的类型如下:

foo :: CharParser st Foo

CharParser 已定义 here如:

type CharParser st = GenParser Char st

CharParser 因此是涉及 GenParser 的类型同义词，其本身定义 here如:

type GenParser tok st = Parsec [tok] st

GenParser 是另一种类型同义词，使用 Parsec 分配，定义为 here如:

type Parsec s u = ParsecT s u Identity

因此，Parsec 是 ParsecT 的部分应用，其本身已列出 here类型:

data ParsecT s u m a

连同文字:

"ParsecT s u m a is a parser with stream type s, user state type u, underlying monad m and return type a."

底层的 monad 是什么？特别是，当我使用 CharParser 解析器时会发生什么？我看不到它插入堆栈中的位置。和Monadic Parsing in Haskell中list monad的使用有关系吗从不明确的解析器返回多个成功的解析？

Answer 1

在您的情况下，底层 monad 是 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 ( token 流 t )并返回包装在您的 monad 中的结果。这允许人们在获取下一个 token 的同时甚至在获取下一个 token 的过程中做有趣的事情。

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

3. 最后，RunParsecT 和 friend 的最终结果(直到您构建到 m 被 Identity 替换的点)返回包装在这个 monad 中的结果。

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

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

出于效率考虑，Parsec 选择了 Hutton 和 Meijer 的结果列表中的第一个匹配结果。这让它扔掉 Hutton 和 Meijer 列表尾部未使用的结果以及 token 流的前端，因为我们从不回溯。以秒差距为单位，给定组合解析器 a <|> b ，如果a消耗任何输入 b永远不会被评价。解决这个问题的方法是 try这会将状态重置回原来的状态，如果 a失败然后评估 b .

您在评论中询问这是否是使用 Maybe 完成的或Either 。答案是“几乎但不完全是”。如果你看看低杠杆run*您会看到它们返回一个代数类型，该类型告诉天气输入已被消耗，然后一秒钟给出结果或错误消息。这些类型的工作方式类似于 Either ，但即使它们也没有直接使用。我将向您推荐the post，而不是进一步扩展它。作者:Antoine Latter，解释了它是如何工作的以及为什么这样做。