Обнаружение ошибок и отчетность с использованием Maybe

Question

Я пишу пропозициональный логический парсер в Haskell. Сейчас я занимаюсь разбором рук в качестве учебного упражнения. В конце концов я займусь парсеком. Между тем, я пытаюсь склонить голову к Монадам. В частности, я использую Maybe для сообщения об ошибках из моей функции parse. Моя текущая беда в том, с частью вспомогательной функции: (. Для справки, полный parse функция может быть найдена here)

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 

Этот код разбирает предложение о форме [ A | B ] где A и B являются любые произвольные предложения. Как вы можете видеть, я использую аппликативный стиль в последней строке для распространения результата Nothing, если предыдущий рекурсивный вызов приводит к Nothing. Это позволило мне вынуть a == Nothing и b == Nothing из условия if. Как я могу использовать Applicative или Monad экземпляр Maybe для свертывания остальной части этого if?

Answer 1

Вы можете использовать функцию от Control.Monad по имени guard. Это имеет немного странный тип:

guard :: MonadPlus m => Bool -> m() 

MonadPlus охватывает все монады, которые имеют некоторые «пустой» случай. Для списков это []; для Maybe это Nothing. guard принимает значение boolean; если он равен 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.

Answer 2

Я действительно сделаю проблему в обратном порядке: я начну с монадического решения и вернусь от него к ручному решению. Это приведет к тому же коду, который вы получите, если вручную придете к правильному решению.

Типичный тип подписи монадическое парсер имеет вид:

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.

Как только мы получим этот примитивный синтаксический анализатор, мы можем определить все остальные синтаксические анализаторы, используя интерфейс StateTMonad. Например, давайте определим синтаксический анализатор, который соответствует одному символу:

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',"") 

Работа Backwards

Это подводит нас к первоначальному вопросу: Как вы вручную написать такое же поведение? Мы будем работать назад от 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 

Теперь мы распространяем внешний заявление случай более внутренний вопрос:

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 экземпляры вообще.

Заключительный Parser

Я теперь повторить этот процесс для последней функции, но оставить вывод как упражнение для вас:

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 или неполный шаблон совпадает. Кроме того, код, который вы написали, не компилируется, но даже если бы он это сделал, он все равно дал бы неправильное поведение.

Answer 3

Основываясь на answer by @TikhonJelvis, я обновил всю мою функцию parse. (The parse' функция от ФП в предложении о parsewhere.) Первая редакция использует делать обозначения и `охранник

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