понеділок, 18 березня 2013 р.

Why laziness matters

По мотивам лекции. Там Эрик пишет функциональный парсер, а для типа возвращаемого значения использует список. Я решил углубиться в реализацию, поэкспериментировать, начал писать, но не имея понятия зачем там список, решил использовать 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 возвращает список: каждый элемент – это попытка.

2 коментарі:

  1. Век живи, век учись, про -XTupleSections не знал

    ВідповістиВидалити
    Відповіді
    1. А вы пробуйте интуитивно, если чего то хотите, а компилятор вам скажет, мол забыли опцию.

      Видалити