如何使用只接受唯一元素的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函數。雖然在這個問題上所陳述的問題並不相同，但它理論上可以解決我的問題。但是我不明白的是我如何在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需要二次時間。但是，這種方法很有效，它可能不足以解析中小文件：即大多數東西都是手工編寫的，而不是自動生成的。