HaskellのReadPの使用方法を修正しました。

Question

HaskellのReadPを使用して、ファイル内の数字のリストに対して非常に単純なパーサーを行いました。それは動作しますが、非常に遅いです...このタイプのパーサーのこの通常の動作ですか、何か間違っていますか？

Answer 1

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 

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 ] 

を有効な全ファイルの解析を抽出するには、場合、それは非常に迅速にすべての入力を消費するが、その入力を解釈する百bazillionの方法がありました。あいまいさに気にしない場合は、最初のものが早く到着するため、最初のものを最後のものよりもむしろ返すでしょう。