Uso correcto de ReadP en Haskell

Question

Hice un analizador muy simple para listas de números en un archivo, usando ReadP en Haskell. Funciona, pero es muy lento ... ¿es este comportamiento normal de este tipo de analizador o estoy haciendo algo 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 tiene un comportamiento exponencial, ya que está permitiendo que el espacio en blanco entre los números para ser opcional. Así que para la línea:

12 34 56 

Es ver estos análisis sintácticos:

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

Se podía ver cómo esto podría salirse de control para las líneas largas. ReadP devuelve todos análisis válidos en orden creciente de longitud, por lo que para llegar al último análisis debe recorrer todos estos análisis intermedios. Cambio:

int_list <- integerReader `sepBy1` innocentWhitespace 

Para:

int_list <- integerReader `sepBy1` mandatoryWhitespace 

Para una definición adecuada de mandatoryWhitespace aplastar este comportamiento exponencial. La estrategia de análisis usada por parsec es más resistente a este tipo de error, porque es codiciosa: una vez que consume entrada en una rama determinada, se compromete con esa rama y nunca retrocede (a menos que se lo haya pedido explícitamente). Entonces, una vez que se haya analizado correctamente 12, nunca volverá a analizar el 1 2. Por supuesto, eso significa que importa en qué orden usted declara sus elecciones, lo que siempre me resulta un poco penoso de considerar.

También me gustaría utilizar:

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

Para extraer un análisis sintáctico de todo el archivo válido, en caso de que se consume muy rápidamente todas las entradas pero había un centenar de maneras de interpretar bazillion esa entrada. Si no le importa la ambigüedad, probablemente prefiera devolver la primera que la anterior, porque la primera llegará más rápido.