使用单子来编写简单的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-notation （当然意味着会调用Monad）。我还不太理解do-notation，所以这里是satisfy的desugared版本：

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)如何返回一个Parser（至少应该返回），否则调用它上面的dePsr就没有意义了。而且有rest存在更加令人困惑。即使(k a)返回一个Parser，调用dePsr也会从返回的Parser中提取基础函数，并将rest作为输入传递给它。这显然不会像(>>=)的定义所要求的那样返回Parser b类型的值。显然我在某个地方误解了一些东西。

- Sakeeb Hossain

---

请注意，dePsr(k a) rest 函数位于 q 函数内部。q 函数不是直接由 ... >>= ... 返回的结果。... >>= ... 的结果是 PsrOf q，而不是 q。 - David Young

另外，请注意 k 的类型为 a -> Parser b（可以在注释的类型签名中看到）。因此，如果您给 k 一个 a 值，它将会给您一个 Parser b 值。这就是为什么 k a :: Parser b。 - David Young

Answer 1

好的，也许这会有所帮助。让我们从将一些点放回到dePsr开始。

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

同时，让我们也写出返回值：（注意：为了更加清晰，我会输入所有的点）

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

现在来自于(>>=)定义的Just分支

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

让我们确保我们对每个东西的定义都达成一致：

• rest：在应用p1后剩余未解析的字符串
• a：应用p1的结果
• k :: a -> Parser b：获取先前解析器的结果并创建一个新的解析器
• dePsr：将Parser a解包回到函数`String -> Maybe (String, a)

请记住，我们将在函数顶部再次将其包装回解析器：PsrOf q

所以在英语中，bind（>> =）接受一个名为a的解析器和一个从a到b的解析器函数，并返回一个b解析器。生成的解析器通过将q :: String -> Maybe（String，b）包装在Parser构造函数PsrOf中来创建。然后，组合解析器q使用称为inp的字符串并应用由第一个解析器模式匹配得到的函数p1 :: String -> Maybe（String，a），并对结果进行模式匹配。对于错误，我们传播Nothing（很容易）。如果第一个解析器有结果，我们有两个信息，仍未解析的字符串称为rest和结果a。我们将a给k，第二个解析器组合器，并获得我们需要使用dePsr打开的Parser b。这个函数可以应用于rest以获取组合解析器的最终结果。

我认为阅读这个的最难部分是有时候我们会使用 解析器函数，这使得实际发生的事情变得模糊不清。

好的，对于 satisfy 的例子。

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

"

empty源自备选实例，是PsrOf（const Nothing），因此是一个总是失败的解析器。

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

"

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

因此，在绑定(>>=)的定义中

• p1 = \(c:cs -> Just (cs, c))
• k = (\c -> PsrOf (\rest -> Just (rest, c)))
• q inp = let Just (rest,a) = p1 inp in dePsr (k a) rest，仅针对成功分支

然后q变成了

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

进行一些β-还原

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

最后再清理一些东西

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

如果pred成功，我们将satisfy缩小到完全等于anyChar，这正是我们期望的，也是问题的第一个示例中发现的。我会把证明留给读者（读：我很懒），证明如果inp = ""或pred c = False，那么结果就是Nothing，就像第一个satisfy示例一样。

---

注意：如果你不是在完成课程作业之外的其他任务，从一开始就添加错误处理将使你节省数小时的痛苦和挫折，让你的解析器变成 String -> Either String (String,a)。稍后可以轻松将错误类型更改为更通用的类型，但要将所有内容从 Maybe 更改为 Either 则很麻烦。

---

问题: "你能解释一下在将“点”放回到return后，你是如何得出return a = PsrOf (\rest -> Just (rest, a))的吗？"

答案: 首先，提供Monad实例定义而不包括Functor和Applicative定义是非常不幸的。 pure和return函数必须相同（这是Monad法则的一部分），除了在Haskell历史上Monad比Applicative更早之外，它们将被称为相同的东西。 实际上，我不知道pure看起来像什么，但我知道它必须是唯一可能的定义。 （如果您想了解该语句的证明，请询问，我已阅读论文，并且我知道结果，但我对类型化λ演算并不足够自信以重现结果。）

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

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

一个 Parser 是一个函数，它接受要解析的字符串并返回包含原始字符串中任何未解析部分的值以及 Nothing（如果失败）的构造函数 PsrOf 中的值。上下文是要解析的字符串，因此我们不能更改它。该值当然是传递给 return 的值。解析器总是成功的，因此我们必须返回一个正确的值。

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

rest是上下文，传递时不会改变。

a是我们放入Monad上下文中的值。

为了完整起见，这里还有来自Functor的唯一合理的fmap定义。

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

- John F. Miller

---

我按照你写的一切做了，但是我仍然困惑于在satisfy中单子的应用。你知道我们有k :: a -> Parser b吗？在satisfy中，如果你看下面注释掉的do-notation版本，k函数与(c -> if pred c then return c else empty)相匹配。正如你所建立的那样，k应该接受一些a并返回一个Parser b，但我不明白它在这种情况下如何实现。只有两种结果：return c或empty（指Alternative），它们都不是Parser b类型。 - Sakeeb Hossain

“return c”的类型是“Monad m => m Char”，“empty”的类型是“Alternative m => m Char”。由于您的“Parser”同时具有“Monad”（已显示）和“Applicative”（未显示）实例，因此这两种类型都可以与“Parser Char”统一，因此表达式“if pred c then return c else empty”确实具有类型“Parser Char”。 - K. A. Buhr

这里你没有提供 Parser 的 Alternative 实例，但我认为在这种情况下知道 empty 被定义为 empty = PsrOf $ const Nothing 是有帮助的（也就是说，它是一个“无用”的解析器，对于每个输入都失败了——但是这样的“无用”东西最终会以某种神秘的方式变得非常有用来定义抽象概念）。特别是在 do 块版本中的 else empty 正好对应于其他版本中的 p _ = Nothing。 - Robin Zigmond

@John 最后一个问题：你能解释一下在你把“点”放回到return之后，你是如何得出return a = PsrOf (\rest -> Just (rest, a))的吗？我们怎么能假设使用(\rest -> Just (rest, a))呢？另外，非常感谢你的回答。你解决了很多我的疑惑。 - Sakeeb Hossain

@SakeebHossain，pure或return的定义可以从>>=（甚至是<*>）的定义中计算出来。单子恒等律pure x >>= f = f x和m >>= pure = m告诉你所有你需要知道的。实际上，你只需要一个定律进行计算。我认为这次你最好使用第二个定律。 - dfeuer