По мотивам лекции. Там Эрик пишет функциональный парсер, а для типа возвращаемого значения использует список. Я решил углубиться в реализацию, поэкспериментировать, начал писать, но не имея понятия зачем там список, решил использовать Maybe.
Ниже приведен тип и основные функций для работы с парсером.
data Parser a = Parser { parse :: String -> Maybe (a, String) } instance Monad Parser where return a = Parser $ Just . (a, ) p >>= f = Parser $ \s -> do (a, s) <- parse p s parse (f a) s (+++) :: Parser a -> Parser a -> Parser a p +++ p' = Parser $ \s -> case parse p s of Nothing -> parse p' s r@(Just _) -> r
Но в таком подходе есть проблема: она по мощи уступает регулярным выражениям. Данная реализация применяет парсер к строке только раз. То есть например парсер (anystring >> string "somestring") на любой строке будет возвращать Nothing. Все это по-тому, что парсер не перезапускается. Первый (anystring) парсит любую строку максимальной длинны и ничего не оставляет следующим.
Мысля императивно, у меня возникла идея добавить парсеру состояние, чтоб можно было его перезапускать. Теперь парсер это начальное состояние и функция, возвращающая помимо прочего следующие состояние. Ужас. Ниже реализация тех же функций. Но оно не до конца работает: я так и не дописал правильную реализацию (>>=), текущая игнорирует состояние второго парсера, лишая его таким образом возможности перезапуститься в случае чего.
data Parser a = forall st. Parser st (String -> st -> Maybe (a, String, Maybe st)) instance Monad Parser where return a = Parser () $ const . Just . (a, , Nothing) Parser i p >>= f = Parser i loop where loop s st = do (a, s', st') <- p s st case f a of Parser i' p' -> case p' s' i' of Just (b, s'', _) -> Just (b, s'', st') Nothing -> st' >>= loop s (+++) :: Parser a -> Parser a -> Parser a Parser i p +++ Parser i' p' = Parser (Left i) loop where loop s (Left i) = case p s i of Just (a, s, st) -> Just (a, s, fmap Left st) Nothing -> loop s (Right i') loop s (Right i') = do (a, s, st) <- p' s i' return (a, s, fmap Right st)
Долго бившись головой об стену над проблемой решил завернуть парсер в функцию так чтоб явно не принимать и не передавать состояние. То есть хотелось получить обект, который бы выдавал значение, оставшуюся строку и такой же обект, с инкапсулированным внутри следующим состоянием.
data Restartable a = ... loopParser :: Parser a -> String -> Restartable a getNext :: Restartable a -> Maybe (a, String, Restartable a)
Но это же явная реализация ленивого списка! Парсер должен возвращать список, и никаких состояний. В языках с жадным вычислением такой (Restartable a) объект не эквивалентен списку по понятным причинам, поэтому я и пошел таких путем... А надо было так:
data Parser a = Parser { parse :: String -> [(a, String)] } instance Monad Parser where p >>= f = Parser $ \s -> do (a, s) <- parse p s parse (f a) s return a = Parser $ return . (a,) (+++) :: Parser a -> Parser a -> Parser a p +++ p' = Parser $ \s -> parse p s ++ parse p' s
Думаю разница очевидна. Причем последний вариант работает как и надо было. Вывод: ленивость – один из краеугольных камней композиционности.
Теперь ясно зачем parsec возвращает список: каждый элемент – это попытка.
Век живи, век учись, про -XTupleSections не знал
ВідповістиВидалитиА вы пробуйте интуитивно, если чего то хотите, а компилятор вам скажет, мол забыли опцию.
Видалити