Правильное использование ReadP в Haskell

Question

Я сделал очень простой парсер для списков чисел в файле, используя ReadP в Haskell.Это работает, но очень медленно ... это нормальное поведение парсера такого типа или я что-то не так делаю?

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 имеет экспоненциальное поведение, поскольку допускает использование пробела между числами необязательно . Итак, по строке:

12 34 56

Видит эти разборы:

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

Вы могли видеть, как это могло выйти из-под контроля на длинных линиях. ReadP возвращает все действительные разборы в порядке увеличения длины, поэтому для перехода к последнему разбору необходимо пройти через все эти промежуточные разборы. Изменения:

int_list <- integerReader `sepBy1` innocentWhitespace

Кому:

int_list <- integerReader `sepBy1` mandatoryWhitespace

Для подходящего определения mandatoryWhitespace, чтобы раздавить это экспоненциальное поведение. Стратегия синтаксического анализа, используемая parsec, более устойчива к такого рода ошибкам, потому что она жадная - когда она потребляет входные данные в данной ветви, она фиксируется в этой ветви и никогда не возвращается (если вы явно не попросили об этом). Поэтому, если он правильно проанализировал 12, он никогда не вернется к синтаксическому анализу 1 2. Конечно, это означает, что имеет значение, в каком порядке вы указываете свой выбор, о котором я всегда нахожу немного болезненным.

Также я бы использовал:

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

Чтобы извлечь действительный синтаксический анализ всего файла, в случае, если он очень быстро потребляет все входные данные, но существует сотни способов интерпретации этих входных данных. Если вас не волнует двусмысленность, вам, скорее всего, лучше вернуть первое, чем последнее, потому что первое прибудет быстрее.