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 suma是一个解析器,具有流类型s,用户状态类型u,底层monad m和返回类型a."

什么是潜在的monad？特别是,当我使用CharParser解析器时它是什么？我无法看到它在堆栈中的插入位置.是否存在与使用Haskell中的Monadic Parsing中的列表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(标记流t)并返回包含在monad中的结果.这允许人们在获取下一个令牌的过程中甚至在获取下一个令牌的过程中做有趣的事情.

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

3. 最后,RunParsecT和朋友的最终结果(直到你构建到m被替换的点Identity)返回包含在这个monad中的结果.

这个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中,给定组合解析器a <|> b,如果a消耗任何输入b将永远不会被评估.解决这个问题的方法是try将状态重置回原来的状态,如果a失败然后进行评估b.

您在评论中询问是否使用Maybe或完成此操作Either.答案是"几乎但不完全".如果您查看低杠杆run*功能,您会看到它们返回代数类型,它告诉天气输入被消耗,然后是第二个,它会给出结果或错误消息.这些类型有点像Either,但即使它们不直接使用.而不是进一步扩展这一点,我将引用你的Antoine Latter 的帖子,解释这是如何工作的以及为什么这样做.

Answer 2

GenParser是根据Parsec而不是ParsecT定义的.Parsec依次定义为

type Parsec s u = ParsecT s u Identity

所以答案是当使用CharParser时,底层monad是Identity monad.