gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-02 06:48:37 24 4
gpt4 key购买 nike

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

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

因此,ParsecParsecT 的部分应用,其本身已列出 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的使用有关系吗从不明确的解析器返回多个成功的解析?

最佳答案

在您的情况下,底层 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 的最终结果(直到您构建到 mIdentity 替换的点)返回包装在这个 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,解释了它是如何工作的以及为什么这样做。

关于parsing - 底层秒差距单子(monad),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8054157/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com