parsing - 最小纯应用解析器

Question

我试图弄清楚如何基于一个简单的 parser 构建一个“纯应用解析器”执行。解析器在其实现中不会使用 monad。我之前问过这个问题，但错误地回答了这个问题，所以我再试一次。

这里是基本类型及其 Functor、Applicative 和 Alternative 实现:

newtype Parser a = Parser { parse :: String -> [(a,String)] }

instance Functor Parser where
  fmap f (Parser cs) = Parser (\s -> [(f a, b) | (a, b) <- cs s])

instance Applicative Parser where
  pure = Parser (\s -> [(a,s)])
  (Parser cs1) <*> (Parser cs2) = Parser (\s -> [(f a, s2) | (f, s1) <- cs1 s, (a, s2) <- cs2 s1])

instance Alternative Parser where
  empty = Parser $ \s -> []
  p <|> q = Parser $ \s ->
    case parse p s of
      [] -> parse q s
      r  -> r

item 函数从流中取出一个字符:

item :: Parser Char
item = Parser $ \s ->
  case s of
   [] -> []
   (c:cs) -> [(c,cs)]

此时，我想实现digit。我当然可以这样做:

digit = Parser $ \s ->
  case s of
    [] -> []
    (c:cs) -> if isDigit c then [(c, cs)] else []

但我正在复制item的代码。我想基于 item 实现 digit。

如何实现digit，使用item从流中取出一个字符，然后检查该字符是否是数字，而不将单子(monad)概念引入其中实现？

Answer 1

首先，让我们写下我们目前手头上的所有工具:

-- Data constructor
Parser :: (String -> [(a, String)]) -> Parser a

-- field accessor
parse :: Parser a -> String -> [(a, String)]

-- instances, replace 'f' by 'Parser'
fmap  :: Functor f     =>   (a -> b) -> f a -> f b
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
pure  :: Applicative f =>                 a -> f a

-- the parser at hand
item :: Parser Char

-- the parser we want to write with item
digit :: Parser Char
digit = magic item

-- ?
magic :: Parser Char -> Parser Char

当前真正的问题是“什么是magic”？我们能用的东西就这么多。其类型表示fmap ，但我们可以排除这种可能性。我们所能提供的只是一些功能a -> b ，但没有f :: Char -> Char这使得fmap f表示失败。

怎么样(<*>) ，这有帮助吗？好吧，再说一遍，答案是否定的。我们在这里唯一能做的就是获取 (a -> b)脱离上下文并应用它；无论这在给定的上下文中意味着什么 Applicative 。我们可以统治pure出来。

问题是我们需要检查 Char那item可能会解析并更改上下文。我们需要像 Char -> Parser Char 这样的东西

但我们没有统治Parser或parse出来!

magic p = Parser $ \s ->
  case parse p s of -- < item will be used here
    [(c, cs)] -> if isDigit c then [(c, cs)] else []
    _         -> []

是的，我知道，这是重复的代码，但现在它使用 item 。它正在使用 item在检查角色之前。这是我们可以使用item的唯一方法。这里。现在，隐含了某种序列: item必须先成功digit可以做它的工作。

或者，我们可以尝试这种方式:

digit' c :: Char -> Parser Char
digit' c = if isDigit c then pure c else empty

然后fmap digit' item类型为 Parser (Parser Char) ，它只能通过类似 join 的函数折叠。这就是为什么monads are more powerful than applicative .

话虽如此，如果您首先使用更通用的函数，则可以绕过所有 monad 要求:

satisfy :: (Char -> Bool) -> Parser Char
satisfy = Parser $ \s -> 
   case s of
     (c:cs) | p c -> [(c, cs)]
     _            -> []

然后您可以定义 item和digit就satisfy而言:

item  = satisfy (const True)
digit = satisfy isDigit

这样digit不必检查先前解析器的结果。