使用 monad 进行简单的 Haskell 解析器

Question

长话短说

我试图理解这是怎么回事：

satisfy :: (Char -> Bool) -> Parser Char
satisfy pred = PsrOf p
  where
    p (c:cs) | pred c = Just (cs, c)
    p _ = Nothing

相当于这样：

satisfy :: (Char -> Bool) -> Parser Char
satisfy pred = do
    c <- anyChar
    if pred c then return c else empty

语境

这是一些关于 Haskell 解析的讲义的片段，我试图理解：

import Control.Applicative
import Data.Char
import Data.Functor
import Data.List

newtype Parser a = PsrOf (String -> Maybe (String, a))
    -- Function from input string to:
    --
    -- * Nothing, if failure (syntax error);
    -- * Just (unconsumed input, answer), if success.

dePsr :: Parser a -> String -> Maybe (String, a)
dePsr (PsrOf p) = p

-- Monadic Parsing in Haskell uses [] instead of Maybe to support ambiguous
-- grammars and multiple answers.

-- | Use a parser on an input string.
runParser :: Parser a -> String -> Maybe a
runParser (PsrOf p) inp = case p inp of
                            Nothing -> Nothing
                            Just (_, a) -> Just a
                          -- OR: fmap (\(_,a) -> a) (p inp)

-- | Read a character and return. Failure if input is empty.
anyChar :: Parser Char
anyChar = PsrOf p
  where
    p "" = Nothing
    p (c:cs) = Just (cs, c)

-- | Read a character and check against the given character.
char :: Char -> Parser Char
-- char wanted = PsrOf p
--   where
--     p (c:cs) | c == wanted = Just (cs, c)
--     p _ = Nothing
char wanted = satisfy (\c -> c == wanted)   -- (== wanted)

-- | Read a character and check against the given predicate.
satisfy :: (Char -> Bool) -> Parser Char
satisfy pred = PsrOf p
  where
    p (c:cs) | pred c = Just (cs, c)
    p _ = Nothing
-- Could also be:
-- satisfy pred = do
--     c <- anyChar
--     if pred c then return c else empty

instance Monad Parser where
    -- return :: a -> Parser a
    return = pure

    -- (>>=) :: Parser a -> (a -> Parser b) -> Parser b
    PsrOf p1 >>= k = PsrOf q
      where
        q inp = case p1 inp of
                  Nothing -> Nothing
                  Just (rest, a) -> dePsr (k a) rest

我理解直到 Monad 定义的最后一位为止的所有内容，特别是我不明白以下行如何返回定义Parser b所需的类型(>>=)：

Just (rest, a) -> dePsr (k a) rest

如果没有例子，我很难理解 Monad 定义的含义。值得庆幸的是，我们在该satisfy函数的替代版本中有一个，它使用 do 表示法（这当然意味着 Monad 正在被调用）。我真的还不明白 do 符号，所以这是脱糖版本satisfy：

satisfy pred = do
    anyChar >>= (c ->
    if pred c then return c else empty)

所以根据我们(>>=)定义的第一行，即

PsrOf p1 >>= k = PsrOf q

我们有anyChar作为我们的PsrOf p1和(c -> if pred c then return c else empty)作为我们的k。我不明白的是如何dePsr (k a) rest返回(k a)a Parser（至少它应该，否则调用dePsr它就没有意义）。的存在使这变得更加混乱rest。即使(k a)返回 a Parser，调用dePsr也会从返回中提取底层函数Parser并将rest其作为输入传递给它。Parser b这绝对不会返回的定义所要求的类型(>>=)。显然我在某个地方误解了一些东西。

Answer 1

好吧，也许这会有所帮助。让我们首先将一些点放回dePsr。

\n\n

dePsr :: Parser a -> String -> Maybe (String, a)\ndePsr (PsrOf p) rest = p rest\n

\n\n

让我们也写出回报：（注意，为了清楚起见，我输入了所有要点）

\n\n

return :: a -> Parser a\nreturn a = PsrOf (\\rest -> Just (rest, a))\n

\n\n

现在从Just分支(>>=)定义

\n\n

 Just (rest, a) -> dePsr (k a) rest\n

\n\n

让我们确保我们对每件事都达成一致：

\n\n

\n
• rest之后仍未解析的字符串p1应用
\n
• a申请的结果p1
\n
• k :: a -> Parser b获取前一个解析器的结果并创建一个新的解析器
\n
• dePsr打开一个Parser a拆回函数 `String -> Maybe (String, a)
\n

\n\n

请记住，我们将把它包起来在函数顶部再次PsrOf q

\n\n

因此，在英语中，bind(>>=)接受一个解析器 ina和一个函数 froma到一个解析器 inb并返回一个解析器 in b。生成的解析器是通过包装q :: String -> Maybe (String, b)Parser 构造函数来生成的PsrOf。然后q，组合解析器接受String调用inp并应用我们从第一个解析器的模式匹配中获得的函数p1 :: String -> Maybe (String,a)，并对结果进行模式匹配。对于错误，我们传播Nothing（简单）。如果第一个解析器有结果，我们有两条信息，即尚未解析的字符串调用rest和结果a。我们给a第二k个解析器组合器 ，并得到 a Parser b，我们需要用它来解包dePsr以获取函数（String -> Maybe (String,b)返回。该函数可以应用于rest组合解析器的最终结果。

\n\n

我认为阅读本文最困难的部分是有时我们会咖喱解析器函数，这掩盖了实际发生的事情。

\n\n

好的satisfy例子

\n\n

satisfy pred \n  = anyChar >>= (c -> if pred c then return c else empty)\n

\n\n

empty来自替代实例并且是PsrOf (const Nothing)因此解析器总是失败。

\n\n

让我们只看成功的分支。仅替换成功的部分：

\n\n

PsrOf (\\(c:cs) ->Just (cs, c)) >>= (\\c -> PsrOf (\\rest -> Just (rest, c)))\n

\n\n

所以在绑定(>>=)定义中

\n\n

\n
• p1 = \\(c:cs -> Just (cs, c))
\n
• k = (\\c -> PsrOf (\\rest -> Just (rest, c)))
\n
• q inp = let Just (rest,a) = p1 inp in dePsr (k a) rest再次只有成功的分支
\n

\n\n

然后就q变成了

\n\n

q inp = \n  let Just (rest, a) = (\\(c:cs) -> Just (cs, c)) inp\n   in dePsr (\\c -> PsrOf (\\rest -> Just (rest, c))) a rest\n

\n\n

做一些 \xce\xb2-reduction

\n\n

q inp =\n let (c:cs) = inp\n     rest = cs\n     a = c\n  in dePsr (PsdOf (\\rest -> Just (rest, a))) rest -- dePsr . PsrOf = id\n

\n\n

终于又清理了一些

\n\n

q (c:cs) = Just (cs, c) \n

\n\n

因此，如果pred成功，我们就会还原satisfy到anyChar我们所期望的，以及我们在问题的第一个例子中发现的。我将把它留给读者（阅读：我很懒）来证明 if 或inp = ""thepred c = False结果Nothing如第一个satisfy示例中所示。

\n\n\n\n

注意：如果你正在做除课堂作业以外的任何事情，你可以通过从一开始就进行错误处理来节省自己数小时的痛苦和沮丧，使你的解析器String -> Either String (String,a)很容易使错误类型稍后变得更通用，但需要更改 PITA一切从Maybe到Either。

\n\n\n\n

问题： “[C]你能解释一下你是如何return a = PsrOf (\\rest -> Just (rest, a))从return = pure在将“积分”放回回报后

\n\n

回答：首先，在没有 Functor 和 Applicative 定义的情况下给出 Monad 实例定义是非常不幸的。和功能必须相同（这是 Monad 定律的一部分），并且它们将被称为相同的东西，pure除了returnMonad早于 Haskell 历史中的 Applicative事实上，我不“知道”纯粹是什么样子，但我知道它必须是什么，因为它是唯一可能的定义。（如果你想了解该陈述的证明，请询问，我已经阅读了论文，并且我知道结果，但我对类型化 lambda 演算还没有足够的了解，无法有信心重现结果。）

\n\n

return必须在上下文中包装一个值，而不需要改变上下文。

\n\n

return :: Monad m => a -> m a\nreturn :: a -> Parser a -- for our Monad\nreturn :: a -> PsrOf(\\str -> Maybe (rest, value)) -- substituting the constructor (PSUDO CODE)\n

\n\n

AParser是一个函数，它接受要解析的字符串并返回Just值以及原始字符串或Nothing on failure, all wrapped in the constructorPsrOf的任何未解析部分. The context is the string to be parsed, so we cannot change that. The value is of course what was passed to return` 的任何未解析部分。解析器总是成功，所以我们必须返回一个值。

\n\n

return a =  PsrOf (\\rest -> Just (rest, a))\n

\n\n

rest是上下文并且它不加改变地传递。\na是我们放入 Monad 上下文中的值。

\n\n

为了完整起见，这里也是唯一合理的定义fmapFunctor 的唯一合理定义。

\n\n

fmap :: Functor f => (a->b) -> f a -> f b\nfmap :: (a -> b) -> Parser a -> Parser b -- for Parser Monad\nfmap f (PsrOf p) = PsrOf q\n  where q inp = case p inp of\n    Nothing -> Nothing\n    Just (rest, a) -> Just (rest, f a)\n  -- better but less instructive definition of q\n  -- q = fmap (\\(rest,a) -> (rest, f a)) . p\n

\n