最小纯粹适用的解析器 [英] Minimal Purely Applicative Parser

问题描述

我试图找出如何基于一个简单的构建一个纯粹适用的解析器解析器的实现。解析器不会在其实现中使用monad。我以前问过这个问题，但错误地构思了它，所以我再次尝试。

以下是基本类型及其 Functor ， Applicative 和替代实现：

  newtype Parser a = Parser {parse： ：字符串 - > [（a，String）]} 
 
实例Functor Parser其中
 fmap f（Parser cs）= Parser（\ s  - > [（fa，b）|（a，b ）<  -  cs s]）
 
实例应用解析器其中
 pure = Parser（\ s  - > [（a，s）]）
（Parser cs1） < * GT; （解析器cs2）=解析器（\\ ss）> [（fa，s2）|（f，s1）< -  cs1s，（a，s2）< -  cs2s1]）$ ​​b 
 $ b instance Alternative Parser其中
 empty = Parser $ \s  - > [] 
 p< |> q =解析器$ \s  - > 
案例解析p 
 []  - >解析q s 
 r  - > r 
  

项函数关闭一个字符流：

  item :: Parser Char 
 item = Parser $ \s  - > 
案例s 
 []  - > [] 
（c：cs） - > [（c，cs）] 
  

此时，我想实现位。我当然可以这样做：

  digit = Parser $ \s  - > 
案例s 
 []  - > [] 
（c：cs） - >如果isDigit c然后[（c，cs）] else [] 
  

但我复制代码项目。我想根据 item 实现 digit 。

如何使用 item 从字符串中取出一个字符然后检查以查看实现 digit 的方法如果字符是一个数字而没有将monadic概念引入到实现中？ 首先，让我们写下我们目前所有的工具

   - 数据构造函数
 Parser ::（String  - > [（a，String） ]） - >解析器a 
 
  - 字段存取器
解析::解析器a  - >字符串 - > [（a，String）] 
 
  - 实例，用'Parser'替换'f'
 fmap :: Functor f => （a  - > b） - > f a  - > f b 
（*）::适用的f => f（a  - > b） - > f a  - > f b 
 pure :: Applicative f => a  - > fa 
 
  - 手头解析器
 item :: Parser Char 
 
  - 我们希望用item 
 digit :: Parser编写的解析器Char 
数字=魔术物品
 
  - ？ 
 magic :: Parser Char  - > Parser Char 
  

真正的问题在于什么是 magic ？只有很多东西我们可以使用。它的类型表示 fmap ，但我们可以排除这一点。我们所能提供的只是一些功能 a - > b ，但没有 f :: Char - >使$ fmap f 的char 表示失败。

（< *>），这可以帮助吗？那么，答案是否定的。我们唯一能做的就是从上下文中取出（a - > b）并应用它;无论在给定 Applicative 的情况下如何。我们可以规定 pure out。

问题是我们需要检查 Char item 可能会解析和更改上下文。我们需要像 Char - > Parser Char

但我们并没有规定 Parser 或解析 out！

  magic p = Parser $ \s  - > 
案例分析 - <<项目将在这里使用
 [（c，cs）]  - >如果isDigit c那么[（c，cs）] else [] 
 _  - > [] 
  

是的，我知道，它是重复的代码，但现在它使用项目。它在检查字符之前使用 item 。这是我们可以在这里使用 item 的唯一方法。现在，有一些顺序暗示： item 必须在 digit 之前成功才能工作。

或者，我们可以这样试试：

  digit' c :: Char  - >解析器char 
数字'c = if isDigit c then pure c else empty 
  

但是 fmap digit'item 应该有类型 Parser（Parser Char），它只能通过类似连接的函数。这就是为什么 monads比应用更强大。

如果你先使用一个更一般的函数，你可以解决所有的monad需求：

  satisfy ::（char  - > Bool） - >解析器Char 
满足= Parser $ \s  - > 
案例的
（c：cs）| p c  - > [（c，cs）] 
 _  - > [] 
  

然后您可以定义项目和数字以满足：

  item = satisfy（const True）
数字=满足isDigit 
  

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

I'm trying to figure out how to build a "purely applicative parser" based on a simple parser implementation. The parser would not use monads in its implementation. I asked this question previously but mis-framed it so I'm trying again.

Here is the basic type and its Functor, Applicative and Alternative implementations:

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 function takes a character off the stream:

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

At this point, I want to implement digit. I can of course do this:

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

but I'm replicating the code of item. I'd like to implement digit based on item.

How do I go about implementing digit, using item to take a character off the stream and then checking to see if the character is a digit without bringing monadic concepts into the implementation?

解决方案

First, let us write down all the tools we currently have at hand:

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

The real question at hand is "what is magic"? There are only so many things we can use. Its type indicates fmap, but we can rule that out. All we can provide is some function a -> b, but there is no f :: Char -> Char that makes fmap f indicate a failure.

What about (<*>), can this help? Well, again, the answer is no. The only thing we can do here is to take the (a -> b) out of the context and apply it; whatever that means in the context of the given Applicative. We can rule pure out.

The problem is that we need to check the Char that item might parse and change the context. We need something like Char -> Parser Char

But we didn't rule 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 []
    _         -> []

Yes, I know, it's duplicate code, but now it's using item. It's using item before inspecting the character. That's the only way we can use item here. And now, there is some kind of sequence implied: item has to succeed before digit can do it's work.

Alternatively, we could have tried this way:

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

But then fmap digit' item would have the type Parser (Parser Char), which can only get collapsed with a join-like function. That's why monads are more powerful than applicative.

That being said, you can get around all of the monad requirements if you use a more general function first:

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

You can then define both item and digit in terms of satisfy:

item  = satisfy (const True)
digit = satisfy isDigit

That way digit does not have to inspect the result of a previous parser.

这篇关于最小纯粹适用的解析器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！