解构` `Maybe (a，b)`

Question

类似于我的last question的后续版本。我正在学习Brent Yorgey的Haskell课程，我正在尝试解决一个练习，该练习要求我们为以下类型创建一个Applicative实例：

newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

runParser解析一个字符串并返回一个令牌和剩余的字符串。在这种情况下，p1 <*> p2应该将runParser p1生成的函数应用于runParser p2生成的令牌(在运行runParser p1之后应用于字符串的左侧)。

到目前为止，我有：

(Parser { runParser = run }) <*> (Parser { runParser = run' }) = Parser run''
  where run'' s = (first <$> f) <*> (s' >>= run')
          where f = fst <$> run s
                s' = snd <$> run s

(first <$> f) <*> (s' >>= run')在我看来相当简洁，但是嵌套的where和run s的奇怪解构看起来有点不对劲。有没有更好的方式来写这个？

Answer 1

首先，让我稍微重写一下，以避免模式匹配：

p <*> q = Parser run
  where run s = (first <$> f) <*> (s' >>= runParser q)
          where f = fst <$> runParser p s
                s' = snd <$> runParser p s

在这里，我简单地使用了字段访问器runParser :: Parser a -> String -> Maybe (a, String)，而不是直接对参数进行模式匹配。这被认为是在Haskell中访问newtyped函数的一种更常用的方法。

接下来，可以进行一些明显的简化，特别是内联一些函数：

p <*> q = Parser $ \s -> (first <$> f) <*> (s' >>= runParser q)
  where
    f = fst <$> runParser p s
    s' = snd <$> runParser p s

(请注意，现在必须将s显式传递给where块中的函数，以便它们可以访问它。别担心，我会马上把它处理掉的。)

这个实现中令人困惑的一件事是嵌套的应用程序和monads。我将略微重写这一部分，以使其更清晰：

p <*> q = Parser $ \s ->
    let qResult = s' s >>= runParser q
    in first <$> f s <*> qResult
  where
    f s = fst <$> runParser p s
    s' s = snd <$> runParser p s

接下来，让我们去掉那些烦人的f和s'定义。我们可以使用模式匹配来做到这一点。通过对runParser p s的输出进行模式匹配，我们可以直接访问这些值：

p <*> q = Parser $ \s ->
    case runParser p s of
        Nothing -> Nothing 
        Just (f, s') ->
            let qResult = runParser q s'
            in first f <$> qOutput

(请注意，由于Maybe中不再有f和s'，因此以前所需的许多应用程序和单行管道现在都不再需要。一个<$>仍然存在，因为runParser q s'仍然可能失败)。

让我们稍微重写一下，通过内联qResult

p <*> q = Parser $ \s ->
    case runParser p s of
        Nothing -> Nothing 
        Just (f, s') -> first f <$> runParser q s'

现在观察这段代码中的一个模式。它执行runParser p s，如果失败则失败；否则它在另一个可能失败的计算中使用该值。这听起来就像是一元排序！所以让我们用>>=重写它

p <*> q = Parser $ \s -> runParser p s >>= \(f, s') -> first f <$> runParser q s'

最后，为了提高可读性，整个代码可以用do-notation重写：

p <*> q = Parser $ \s -> do
     (f, s') <- runParser p s
     qResult <- runParser q s'
     return $ first f qResult

更容易阅读！这个版本的特别之处在于，它很容易看到发生了什么-运行第一个解析器，获得它的输出，并使用它来运行第二个解析器，然后组合结果。

Answer 2

在我看来，只使用基本模式匹配来保持简单，而不过多地依赖于<*>、<$>、first和其他库函数，这并不丢人。

Parser pF <*> Parser pX = Parser $ \s -> do
   (f, s' ) <- pF s
   (x, s'') <- pX s'
   return (f x, s'')

上面的do块位于Maybe monad中。