Korrekte ReadP-Verwendung in Haskell

Question

Ich habe einen sehr einfachen Parser für Listen von Zahlen in einer Datei, mit ReadP in Haskell. Es funktioniert, aber es ist sehr langsam ... ist das normale Verhalten dieser Art von Parser oder mache ich etwas falsch?

import Text.ParserCombinators.ReadP 
import qualified Data.IntSet as IntSet 
import Data.Char 

setsReader :: ReadP [ IntSet.IntSet ] 
setsReader = 
    setReader `sepBy` (char '\n') 

innocentWhitespace :: ReadP() 
innocentWhitespace = 
    skipMany $ (char ' ') <++ (char '\t') 

setReader :: ReadP IntSet.IntSet 
setReader = do 
    innocentWhitespace 
    int_list <- integerReader `sepBy1` innocentWhitespace 
    innocentWhitespace 
    return $ IntSet.fromList int_list 

integerReader :: ReadP Int 
integerReader = do 
    digits <- many1 $ satisfy isDigit 
    return $ read digits 

readClusters:: String -> IO [ IntSet.IntSet ] 
readClusters filename = do 
    whole_file <- readFile filename 
    return $ (fst . last) $ readP_to_S setsReader whole_file 

Answer 1

setReader hat exponentielles Verhalten, weil es die Leerzeichen zwischen den Zahlen wird ermöglicht optional zu sein. Also für die Zeile:

12 34 56 

Es ist zu sehen, diese Parsen:

[1,2,3,4,5,6] 
[12,3,4,5,6] 
[1,2,34,5,6] 
[12,34,5,6] 
[1,2,3,4,56] 
[12,3,4,56] 
[1,2,34,56] 
[12,34,56] 

Sie konnten sehen, wie dies aus der Hand für lange Leitungen bekommen. ReadP gibt alle gültige Parser in ansteigender Reihenfolge zurück. Um also zum letzten Parse zu gelangen, müssen Sie alle diese Zwischenpars durchlaufen. Wechsel:

int_list <- integerReader `sepBy1` innocentWhitespace 

An:

int_list <- integerReader `sepBy1` mandatoryWhitespace 

Für eine geeignete Definition von mandatoryWhitespace dieses exponentiellen Verhalten zerquetschen. Die Parsing-Strategie, die von Parsec verwendet wird, ist resistenter gegen diese Art von Fehler, da sie gierig ist - sobald sie Eingaben in einem bestimmten Zweig verbraucht, wird sie an diesen Zweig gebunden und geht niemals zurück (es sei denn, Sie haben explizit danach gefragt). Sobald es 12 richtig geparst hat, würde es nie wieder zum Parsen gehen. Natürlich bedeutet das, dass es wichtig ist, in welcher Reihenfolge du deine Entscheidungen festlegst, was ich immer als etwas Schmerz empfinde.

Auch würde ich verwenden:

head [ x | (x,"") <- readP_to_S setsReader whole_file ] 

eine gültige Voll Datei Parse zu extrahieren, es ist sehr schnell, falls alle Eingaben verbraucht, aber es hundert bazillion Wege waren, dass die Eingabe zu interpretieren. Wenn Sie sich nicht um die Mehrdeutigkeit kümmern, würden Sie wahrscheinlich lieber die erste als die letzte zurückgeben, weil die erste schneller ankommen wird.