如何使用仅接受唯一元素的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 '"'

这对我来说很好,因为它能够解析我在上面定义的字符串.尽管如此,我现在想强制执行这样一条规则:该集合中的每个元素都必须是唯一的,这就是我遇到麻烦的地方.我在互联网上搜索时发现的第一个结果之一是这个,它建议使用该nub功能.虽然这个问题中提到的问题不一样,但理论上它可以解决我的问题.但我不明白的是我如何在Parser中应用这个功能.我已经尝试将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 ()

该函数采用布尔值.如果它是真的,它返回()并且整个计算(在这种情况下是解析)不会失败.如果它是假的,整个事情都会失败.

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

要做到这一点,我们要做的第一件事是编写一个谓词,检查列表的每个元素是否都是唯一的.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需要二次时间.然而,这可行,并且它可能足以解析中小型文件:即大多数事情是手工编写而不是自动生成.