Обнаружение ошибок и создание отчетов с использованием Maybe
Я пишу синтаксический анализатор высказываний в Haskell. Сейчас я выполняю разбор вручную как учебное упражнение. Со временем я займусь Парсек. В то же время я пытаюсь обернуть голову вокруг монад. В частности, я использую Maybe сообщать об ошибках от моего parse функция. Моя текущая проблема связана с частью вспомогательной функции:
parse' :: String -> (Maybe Wff, String)
parse' ('[':rest) = (x, if null rest''
then ""
else tail rest'')
where (a, rest') = parse' rest
(b, rest'') = parse' (if null rest'
then ""
else tail rest')
x = if null rest'
|| null rest''
|| head rest' /= '|'
|| head rest'' /= ']'
then Nothing
else Or <$> a <*> b
(Для справки, полный parse функцию можно найти здесь.)
Этот код анализирует предложение вида [ A | B ] где A а также B любые произвольные предложения. Как вы можете видеть, я использую аппликативный стиль в последней строке для распространения Nothing результат, если предыдущий рекурсивный вызов приводит к Nothing, Это позволило мне вынуть a == Nothing а также b == Nothing от if состояние. Как я могу использовать Applicative или же Monad экземпляр Maybe разрушить остальную часть этого if?
3 ответа
Вы можете использовать функцию из Control.Monad называется guard, Это имеет немного странный тип:
guard :: MonadPlus m => Bool -> m ()
MonadPlus охватывает все монады, которые имеют какой-то "пустой" корпус. Для списков это []; за Maybe это Nothing, guard принимает логическое значение; если это False, это оценивает это пустое значение; в противном случае он оценивается в return (), Такое поведение в основном полезно в do обозначения:
x = do guard (not $ null rest' || null rest'' || head rest' /= '|' || head rest'' /= ']')
Or <$> a <*> b
То, что здесь происходит, просто. Если условие оценивается как True, охранник возвращается Just (), который затем игнорируется в пользу Or <$> a <*> b (так как do обозначения работает). Однако, если условие False, guard возвращается Nothing, который распространяется через остальную часть do нотация, чтобы дать вам конечный результат Nothing: именно то, что вы хотели.
Чтобы сделать код более читабельным, я бы вытащил условие в свою собственную переменную в where блок.
На самом деле я решу проблему задом наперед: я начну с монадического решения и перейду от него к ручному решению. Это приведет к тому же коду, который вы получите, если получите правильное решение вручную.
Типичная сигнатура типа монадического парсера имеет вид:
type Parser a = String -> Maybe (a, String)
Обратите внимание на небольшую разницу с вашей формой, где у вас есть финал String на внешней стороне Maybe, Оба действительны, но я предпочитаю эту форму больше, потому что я считаю остатки String недействителен, если анализ не удался.
Этот тип на самом деле является частным случаем StateT, который определяется как:
newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }
Обратите внимание, что если мы выберем:
s = String
m = Maybe
... мы вернемся Parser тип:
type Parser a = StateT String Maybe a
-- or: type Parser = StateT String Maybe
Что здорово в этом, так это то, что нам нужно определить только один анализатор вручную, то есть анализатор, который извлекает один символ:
anyChar :: Parser Char
anyChar = StateT $ \str -> case str of
[] -> Nothing
c:cs -> Just (c, cs)
Обратите внимание, что если мы удалили StateT обертка, тип anyChar было бы:
anyChar :: String -> Maybe (Char, String)
Когда мы завернем это StateT это становится:
anyChar :: StateT String Maybe Char
... который просто Parser Char,
Как только мы получим этот примитивный парсер, мы можем определить все остальные парсеры, используя StateT"s Monad интерфейс. Например, давайте определим парсер, который соответствует одному символу:
import Control.Monad
char :: Char -> Parser ()
char c' = do
c <- anyChar
guard (c == c')
Это было просто! guard требует MonadPlus экземпляр для нашей монады, но у нас она уже есть. Причина в том, что благодаря следующим двум MonadPlus экземпляры:
instance (MonadPlus m) => MonadPlus (StateT s m) where ...
instance MonadPlus Maybe where ...
Сочетание этих двух случаев означает, что StateT s Maybe автоматически реализует MonadPlusтак что мы можем использовать guard и он просто волшебным образом сделает "правильную вещь".
С этими двумя парсерами ваш финальный парсер становится очень простым для написания:
data Wff = Or Char Char deriving (Show)
parseWff :: Parser Wff
parseWff = do
char '['
a <- anyChar
char '|'
b <- anyChar
char ']'
return (Or a b)
Это намного яснее и легче понять, что происходит. Это также работает:
>>> runStateT parseWff "[A|B]"
Just (Or 'A' 'B',"")
Работа в обратном направлении
Это подводит нас к исходному вопросу: как вы пишете вручную такое же поведение? Мы будем работать в обратном направлении от Monad а также MonadPlus случаи, чтобы сделать вывод, что они делают для нас под капотом.
Чтобы сделать это, мы должны сделать вывод, что Monad а также MonadPlus случаи для StateT уменьшить, когда его базовая монада Maybe, Давайте начнем с Monad экземпляр для StateT:
instance (Monad m) => Monad (StateT s m) where
return r = StateT (\s -> return (r, s))
m >>= f = StateT $ \s0 -> do
(a, s1) <- runStateT m s0
runStateT (f a) s1
Обратите внимание, что он определен в общих терминах базовой монады. Это означает, что нам также нужно Monad экземпляр для Maybe чтобы получить то, что делает приведенный выше код:
instance Monad Maybe where
return = Just
m >>= f = case m of
Nothing -> Nothing
Just a -> f a
Если мы заменим Maybe экземпляр монады в StateT экземпляр монады мы получаем:
instance Monad (StateT s Maybe) where
return r = StateT (\s -> Just (r, s))
m >>= f = StateT $ \s0 -> case runStateT m s0 of
Nothing -> Nothing
Just (a, s1) -> runStateT (f a) s1
Мы можем сделать то же самое, чтобы вывести Monad экземпляр для StateT s Maybe, Нам просто нужно взять MonadPlus случаи для StateT и `Может быть:
instance (MonadPlus m) => MonadPlus (StateT s m) where
mzero = StateT (\_ -> mzero)
mplus (StateT f) (StateT g) = StateT (\s -> mplus (f s) (g s))
instance MonadPlus Maybe where
mzero = Nothing
mplus m1 m2 = case m1 of
Just a -> Just a
Nothing -> case m2 of
Just b -> Just b
Nothing -> Nothing
... и объединить их в одну:
instance MonadPlus (StateT s Maybe) where
mzero = StateT (\_ -> Nothing)
mplus (StateT f) (StateT g) = StateT $ \s -> case f s of
Just a -> Just a
Nothing -> case g s of
Just b -> Just b
Nothing -> Nothing
Теперь мы можем получить то, что наши парсеры делают под капотом. Давайте начнем с char парсер:
char c' = do
c <- anyChar
guard (c == c')
Это desugars для:
char c' = anyChar >>= \c -> guard (c == c')
Мы только что получили (>>=) делает для StateT s Maybeтак что давайте заменим это в:
char c' = StateT $ \str0 -> case runStateT anyChar str0 of
Nothing -> Nothing
Just (a, str1) -> runStateT ((\c -> guard (c == c')) a) str1
Мы уже знаем определение anyCharИтак, давайте заменим это в:
char c' = StateT $ \str0 -> case runStateT (StateT $ \str -> case str of
[] -> Nothing
c:cs -> Just (c, cs) ) str0 of
Nothing -> Nothing
Just (a, str1) -> runStateT ((\c -> guard (c == c')) a) str1
Мы также знаем, что runStateT обратная StateT, так:
char c' = StateT $ \str0 -> case (\str -> case str of
[] -> Nothing
c:cs -> Just (c, cs) ) str0 of
Nothing -> Nothing
Just (a, str1) -> runStateT ((\c -> guard (c == c')) a) str1
Затем мы можем применить лямбда к str0:
char c' = StateT $ \str0 -> case (case str0 of
[] -> Nothing
c:cs -> Just (c, cs) ) of
Nothing -> Nothing
Just (a, str1) -> runStateT ((\c -> guard (c == c')) a) str1
Теперь мы распределяем внешнюю инструкцию case по внутренней инструкции case:
char c' = StateT $ \str0 -> case str0 of
[] -> case Nothing of
Nothing -> Nothing
Just (a, str1) -> runStateT ((\c -> guard (c == c')) a) str1
c:cs -> case Just (c, cs) of
Nothing -> Nothing
Just (a, str1) -> runStateT ((\c -> guard (c == c')) a) str1
... и оцените утверждения дела:
char c' = StateT $ \str0 -> case str0 of
[] -> Nothing
c:cs -> runStateT ((\c -> guard (c == c')) c) cs
Тогда мы можем применить лямбду к c:
char c' = StateT $ \str0 -> case str0 of
[] -> Nothing
c:cs -> runStateT (guard (c == c')) cs
Чтобы упростить это далее, нам нужно знать, что guard делает. Вот исходный код для этого:
guard pred = if pred then return () else mzero
Мы уже знаем что return а также mzero за StateT s Maybe есть, так что давайте подставим их в:
guard pred = if pred then StateT (\s -> Just ((), s)) else StateT (\_ -> Nothing)
Теперь мы можем включить это в нашу функцию:
char c' = StateT $ \str0 -> case str0 of
[] -> Nothing
c:cs -> runStateT (if (c == c')
then StateT (\s -> Just ((), s))
else StateT (\_ -> Nothing) ) cs
Если мы распространяем runStateT За что мы получаем:
char c' = StateT $ \str0 -> case str0 of
[] -> Nothing
c:cs -> (if (c == c')
then (\s -> Just ((), s))
else (\_ -> Nothing) ) cs
Точно так же мы можем применить обе ветви к cs:
char c' = StateT $ \str0 -> case str0 of
[] -> Nothing
c:cs -> if (c == c') then Just ((), cs) else Nothing
Это эквивалентный код, который мы написали бы вручную, если бы мы не использовали Monad или же MonadPlus экземпляры на всех.
Последний парсер
Теперь я повторю этот процесс для последней функции, но оставлю вывод в качестве упражнения для вас:
parseWff = do
char '['
a <- anyChar
char '|'
b <- anyChar
char ']'
return (Or a b)
parseWff = StateT $ \str0 -> case str0 of
[] -> Nothing
c1:str1 -> if (c1 == '[')
then case str1 of
[] -> Nothing
c2:str2 -> case str2 of
[] -> Nothing
c3:str3 -> if (c3 == '|')
then case str3 of
[] -> Nothing
c4:str4 -> case str4 of
[] -> Nothing
c5:str5 -> if (c5 == ']')
then Just (Or c2 c4, str5)
else Nothing
else Nothing
else Nothing
... но мы можем еще больше упростить это:
parseWff = StateT $ \str0 -> case str0 of
'[':c2:'|':c4:']':str5 -> Just (Or c2 c4, str5)
_ -> Nothing
Обратите внимание, что, в отличие от написанной вами функции, в ней не используются какие-либо частичные функции, такие как tail или неполные совпадения с образцом. Кроме того, код, который вы написали, не компилируется, но даже если бы он это делал, он все равно давал бы неправильное поведение.
Основываясь на ответе @TikhonJelvis, я обновил весь parse функция. (The parse' Функция от ОП в where пункт о parse.) Первая ревизия использует обозначения do и `guard
parse :: String -> Maybe Wff
parse s = do
(x, rest) <- parse' s
guard $ null rest
Just x
where parse' ('~':rest) = do
guard . not $ null rest
(a, rest') <- parse' rest
Just (Not a, rest')
parse' ('[':rest) = do
guard . not $ null rest
(a, rest') <- parse' rest
guard . not $ null rest'
guard $ head rest' == '|'
(b, rest'') <- parse' $ tail rest'
guard . not $ null rest''
guard $ head rest'' == ']'
Just (a `Or` b, tail rest'')
parse' (c:rest) = do
guard $ isLower c
Just (Var c, rest)
parse' [] = Nothing
Некоторые дальнейшие эксперименты помогли мне понять, что я могу заменить все, кроме одного из guard с прямым сопоставлением с образцом:
parse :: String -> Maybe Wff
parse s = do
(x, "") <- parse' s
Just x
where parse' ('~':rest) = do
(a, rest') <- parse' rest
Just (Not a, rest')
parse' ('[':rest) = do
(a, ('|':rest')) <- parse' rest
(b, (']':rest'')) <- parse' rest'
Just (a `Or` b, rest'')
parse' (c:rest) = do
guard $ isLower c
Just (Var c, rest)
parse' [] = Nothing