使用Maybe进行错误检测和报告

Question

我正在用Haskell编写一个命题逻辑解析器。作为一个学习练习，我现在正在手工进行解析。最终我会解决Parsec的问题。同时，我也在尝试用Monad来包装我的大脑。特别是，我使用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

(作为参考，可以在here中找到完整的parse函数。)

这段代码解析形式为[ A | B ]的命题，其中A和B是任意的命题。正如您所看到的，如果前一个递归调用产生Nothing，我在最后一行使用应用样式来传播Nothing结果。这允许我从if条件中去掉a == Nothing和b == Nothing。如何使用Maybe的Applicative或Monad实例来封装此if的其余部分

Answer 1

您可以使用Control.Monad中一个名为guard的函数。这有一个有点奇怪的类型：

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

MonadPlus涵盖了所有有“空”大小写的monads。对于列表，它是[]；对于Maybe，它是Nothing。guard接受一个布尔值；如果为False，则计算结果为该空值；否则计算结果为return ()。此行为在do表示法中最有用：

x = do guard (not $ null rest' || null rest'' || head rest' /= '|' || head rest'' /= ']')
       Or <$> a <*> b

这里发生的事情很简单。如果条件的计算结果为True，则guard返回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。

一旦我们有了原始解析器，我们就可以使用StateT的Monad接口来定义所有其他解析器。

import Control.Monad

char :: Char -> Parser ()
char c' = do
    c <- anyChar
    guard (c == c')

这很简单！guard需要一个monad的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实例开始向后工作，以推断它们在幕后为我们做了什么。

要做到这一点，我们必须推导出当StateT的基单体为Maybe时，StateT的Monad和MonadPlus实例会减少到什么程度。让我们从StateT的Monad实例开始

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的Monad实例来派生上述代码的功能：

instance Monad Maybe where
    return  = Just

    m >>= f = case m of
        Nothing -> Nothing
        Just a  -> f a

如果我们将Maybe monad实例替换为StateT monad实例，我们会得到：

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

我们可以做同样的事情来派生StateT s Maybe的Monad实例。我们只需要使用StateT和``Maybe的MonadPlus实例：

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

这段代码归结为：

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

然后，我们可以将lambda应用于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

..。并对case语句进行评估：

char c' = StateT $ \str0 -> case str0 of
    []   -> Nothing
    c:cs -> runStateT ((\c -> guard (c == c')) c) cs

然后，我们可以将lambda应用于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

我们已经知道了StateT s Maybe的return和mzero是什么，所以让我们将它们替换为：

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或不完整模式匹配。此外，您编写的代码不能编译，但即使编译了，它仍然会给出错误的行为。

Answer 3

基于answer by @TikhonJelvis，我修改了我的整个parse函数。( OP中的parse'函数位于parse的where子句中。)第一个版本使用了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