haskell - 如何使用 Parsec 编写仅接受唯一元素的解析器？

Question

我最近开始学习 Haskell，并一直在尝试 Parsec。然而，在过去的几天里，我一直被一个问题困扰，一直找不到解决方案。所以我想做的是编写一个可以解析这样的字符串的解析器:

<"apple", "pear", "pineapple", "orange">

我为此编写的代码是:

collection :: Parser [String]    
collection = (char '<') *> (string `sepBy` char ',')) <* (char '>')

string :: Parser String
string = char '"' *> (many (noneOf ['\"', '\r', '\n', '"'])) <* char '"'

这对我来说效果很好，因为它能够解析我上面定义的字符串。尽管如此，我现在想强制执行该集合中的每个元素都必须是唯一的规则，这就是我遇到的麻烦。我在互联网上搜索时发现的第一个结果是 this一，建议使用 nub 函数。虽然该问题中提出的问题并不相同，但理论上它可以解决我的问题。但我不明白的是如何在解析器中应用这个函数。我尝试将 nub 函数添加到上面代码的几个部分，但没有成功。后来我也尝试过这样做:

 collection :: Parser [String]
 collection = do
  char '<'
  value <- (string `sepBy` char ','))
  char '>'
  return nub value

但这不起作用，因为类型与 nub 所期望的不匹配，我相信这是我正在努力解决的问题之一。我也不完全确定 nub 是否是正确的方法。我担心我会走错方向，并且无法像这样解决我的问题。也许我缺少什么？任何人可以提供的任何建议或帮助将不胜感激。

Answer 1

秒差距 Parser类型是 MonadPlus 的实例这意味着我们随时都可能失败(即导致解析错误)。一个方便的函数是 guard :

guard :: MonadPlus m => Bool -> m ()

该函数采用 bool 值。如果为 true，则返回 ()并且整个计算(在本例中为解析)不会失败。如果它是假的，那么整个事情就会失败。

因此，只要您不关心效率，这里有一个合理的方法:解析整个列表，检查所有元素是否唯一，如果不是则失败。

为此，我们要做的第一件事是编写一个谓词来检查列表中的每个元素是否唯一。 nub并不完全正确:它返回一个列表，其中删除了所有重复项。但如果我们不太关心性能，我们可以用它来检查:

allUnique ls = length (nub ls) == length ls

有了这个谓词，我们就可以编写一个函数 unique包装任何生成列表的解析器并确保列表是唯一的:

unique parser = do res <- parser
                   guard (allUnique res)
                   return res

同样，如果 guard是给 True ，它不会影响解析的其余部分。但如果给出 False ，这会导致错误。

以下是我们如何使用它:

λ> parse (unique collection) "<interactive>" "<\"apple\",\"pear\",\"pineapple\",\"orange\">"
Right ["apple","pear","pineapple","orange"]
λ> parse (unique collection) "<interactive>" "<\"apple\",\"pear\",\"pineapple\",\"orange\",\"apple\">"
Left "<interactive>" (line 1, column 46):unknown parse error

这就是你想要的。但是，有一个问题:没有提供错误消息。这对用户来说不太友好!幸运的是，我们可以使用 <?> 修复此问题。这是 Parsec 提供的一个运算符，可以让我们设置解析器的错误消息。

unique parser = do res <- parser
                   guard (allUnique res) <?> "unique elements"
                   return res

啊，好多了:

λ> parse (unique collection) "<interactive>" "<\"apple\",\"pear\",\"pineapple\",\"orange\",\"apple\">"
Left "<interactive>" (line 1, column 46):
expecting unique elements

所有这些都有效，但再次值得注意的是，它效率不高。它会在意识到元素不唯一之前解析整个列表，并且 nub需要二次时间。然而，这是有效的，并且对于解析中小型文件来说它可能已经足够好了:即大多数东西都是手工编写的而不是自动生成的。