最小纯应用解析器

我试图找出如何基于一个简单的构建“纯应用解析器”parser http://dev.stephendiehl.com/fun/002_parsers.html执行。解析器在其实现中不会使用 monad。我之前问过这个问题，但错误地回答了这个问题，所以我再试一次。

这是基本类型及其Functor, Applicative and 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

The 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。我想实施digit基于item.

我该如何实施digit, using item从流中取出一个字符，然后检查该字符是否是数字，而不将一元概念引入实现中？

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

-- 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 out.

问题是我们需要检查Char that item可能会解析and改变上下文。我们需要类似的东西Char -> Parser Char

但我们没有统治Parser or parse out!

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 的函数折叠。这就是为什么monad 比 applicative 更强大 https://stackoverflow.com/q/34932624/1139697.

话虽这么说，如果您首先使用更通用的函数，您可以绕过所有 monad 要求：

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

然后您可以定义两者item and digit按照satisfy:

item  = satisfy (const True)
digit = satisfy isDigit

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