Utilisation correcte de ReadP dans Haskell

Question

J'ai fait un analyseur très simple pour les listes de nombres dans un fichier, en utilisant ReadP dans Haskell. Cela fonctionne, mais c'est très lent ... est ce comportement normal de ce type d'analyseur ou est-ce que je fais quelque chose de mal?

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 a un comportement exponentiel, car il permet à l'espace entre les numéros à en option. Donc, pour la ligne:

12 34 56 

Il voit ces Parsis:

[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] 

Vous pouvez voir comment cela pourrait sortir de la main pour les longues lignes. ReadP renvoie tous les analyse correctement dans l'ordre croissant de longueur, donc pour arriver à la dernière analyse, vous devez traverser toutes ces analyses intermédiaires. Changement:

int_list <- integerReader `sepBy1` innocentWhitespace 

Pour:

int_list <- integerReader `sepBy1` mandatoryWhitespace 

Pour une définition appropriée de mandatoryWhitespace de squash ce comportement exponentiel. La stratégie d'analyse utilisée par parsec est plus résistante à ce genre d'erreur, car elle est gourmande - une fois qu'elle consomme une entrée dans une branche donnée, elle est validée sur cette branche et ne revient jamais (à moins que vous ne le demandiez explicitement). Donc, une fois correctement analysé 12, il ne reviendrait jamais à analyser 1 2. Bien sûr, cela signifie qu'il importe dans quel ordre vous énoncez vos choix, ce que je trouve toujours un peu pénible à penser.

Aussi j'utiliser:

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

Pour extraire une analyse syntaxique valide tout fichier, dans le cas où il est très rapidement consommé toutes les entrées, mais il y avait une centaine de façons bazillion d'interpréter cette entrée. Si vous ne vous souciez pas de l'ambiguïté, vous préférerez probablement qu'elle renvoie la première plutôt que la dernière, car la première arrivera plus vite.