Функция Loop в строке слишком длинная - PullRequest
Новая
       16

Функция Loop в строке слишком длинная

0 голосов
/ 27 июня 2018

У меня есть эти функции: 

item :: Parser Char
item  = Parser i
        where i []     = []
              i (x:xs) = [(x,xs)] 

many  :: Eq a=> Parser a -> Parser [a]
many p = many1 p +++ return []

many1  :: Eq a=> Parser a -> Parser [a]
many1 p = do v  <- p
             vs <- many p
             returns (v:vs)

Я получаю странные результаты, применяя разные строки. Если я выполню: 

parse (many item) "x:=0"

я получаю 

[('x',0)]

в то время как если я использую другую строку, более длинную, например, «если x = 0, то x: = 0, иначе x: = 1», это выглядит как зацикливание. Делая некоторые попытки, кажется, что если длина строки больше 19 символов, функция не заканчивается. Это странно, потому что на другой строке длиной менее 19 символов это работает хорошо Что бы это могло быть?

Другие определения: 

newtype Parser a = Parser { parse :: String -> [(a, String)] }


instance Monad Parser where
    return t = Parser $ \s -> [(t, s)]
    m >>= k  = Parser $ \s -> [(x, y) | (u, v) <- parse m s, (x, y) <- parse (k u) v]

(+++) :: Eq a => Parser a -> Parser a -> Parser a
p +++ q = Parser $ \s -> if((parse p s)==[]) then parse q s else parse p s

Ответы [ 2 ]

0 голосов
/ 27 июня 2018

Ваша реализация (+++) не делает то, что вы думаете, что делает. В частности, он вернет только успешный анализ одного из своих аргументов, а не обоих. Вот как сделать то, что вы хотите: 

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = Parser $ \s -> parse p s ++ parse q s

Хотя это не приводит к удалению дубликатов, поэтому имейте в виду, что вы можете получить взрыв разбора, выполнив, например, many (many item).

0 голосов
/ 27 июня 2018

Ваш код работает нормально, просто вы написали, что ваш анализатор имеет бесконечный возврат и, следовательно, O(2^n) время выполнения. Каждый добавляемый вами символ удваивает время, необходимое для завершения: 

$ time hugs foo.hs <<< 'parse (many item) "if x=0 then x:=0 els"'
[...]
Main> [("if x=0 then x:=0 els","")]
Main> [Leaving Hugs]

real    0m11.076s
user    0m10.578s
sys     0m0.016s

против 

$ time hugs foo.hs <<< 'parse (many item) "if x=0 then x:=0 else"'
[...]
Main> [("if x=0 then x:=0 else","")]
Main> [Leaving Hugs]

real    0m22.346s
user    0m22.048s
sys     0m0.036s
...