如何使用 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

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

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

这个函数接受一个布尔值。如果为真，则 return () 并且整个计算（在本例中为解析）不会失败。如果它是假的，整个事情就失败了。

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

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

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 需要二次时间。然而，这是可行的，而且它可能足以解析中小型文件：即大多数东西是手写的而不是自动生成的。

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

How can I write a parser using Parsec that only accepts unique elements?

haskell

functional-programming

parsec