最小纯应用解析器

Question

我正在尝试找出如何基于简单的 parser 实现构建 "purely applicative 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 从流中取出一个字符，然后检查该字符是否为数字，而不将一元概念引入实施中？

Answer 1

仿函数允许您根据某些值进行操作。例如，如果您有一个列表 [1,2,3]，您可以更改其内容。请注意，函子不允许更改结构。 map 无法更改列表的长度。

应用程序允许您组合结构，内容以某种方式融合在一起。 但值不能改变影响结构。

即给定一个item，我们可以改变它的结构，我们可以改变它的内容，但是内容不能改变结构。我们不能选择在某些内容上失败而不是其他内容。

如果有人知道如何更正式和可证明地陈述这一点，我洗耳恭听（这可能与自由定理有关）。

Answer 2

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

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

手头真正的问题是"what is magic"？我们能用的东西只有这么多。它的类型表示 fmap，但我们可以排除这种可能性。我们所能提供的只是一些功能 a -> b，但是没有 f :: Char -> Char 使 fmap f 指示失败。

那(<*>)呢，这个有帮助吗？嗯，再一次，答案是否定的。我们在这里唯一能做的就是从上下文中取出 (a -> b) 并应用它；无论在给定 Applicative 的上下文中意味着什么。我们可以排除 pure。

问题是我们需要检查 item 可能解析和更改上下文的 Char。我们需要像 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)，它只能通过类似连接的函数折叠。这就是为什么 monads are more powerful than applicative.

也就是说，如果您首先使用更通用的函数，则可以绕过所有 monad 要求：

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

然后您可以根据 satisfy:

定义 item 和 digit

item  = satisfy (const True)
digit = satisfy isDigit

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

最小纯应用解析器

Minimal Purely Applicative Parser

monads

parsing

haskell

applicative