Haskell中的组合解析器

Question

我得到了以下解析器

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

instance Functor Parser where
   fmap f p = Parser $ \s -> (\(a,c) -> (f a, c)) <$> parse p s

instance Applicative Parser where
   pure a = Parser $ \s -> Just (a,s)
   f <*> a = Parser $ \s ->
     case parse f s of
       Just (g,s') -> parse (fmap g a) s'
       Nothing -> Nothing

instance Alternative Parser where
   empty = Parser $ \s -> Nothing
   l <|> r = Parser $ \s -> parse l s <|> parse r s

 ensure :: (a -> Bool) -> Parser a -> Parser a
 ensure p parser = Parser $ \s ->
    case parse parser s of
      Nothing -> Nothing
      Just (a,s') -> if p a then Just (a,s') else Nothing

 lookahead :: Parser (Maybe Char)
 lookahead = Parser f
   where f [] = Just (Nothing,[])
         f (c:s) = Just (Just c,c:s)

 satisfy :: (Char -> Bool) -> Parser Char
 satisfy p = Parser f
   where f [] = Nothing
         f (x:xs) = if p x then Just (x,xs) else Nothing

 eof :: Parser ()
 eof = Parser $ \s -> if null s then Just ((),[]) else Nothing

 eof' :: Parser ()
 eof' = ???

我需要编写一个新的解析器eof'，该解析器的功能与eof完全相同，但仅使用给定的解析器和上面的Functor / Applicative / Alternative实例。由于没有组合解析器的经验，因此我一直坚持下去。谁能帮我吗 ？

Answer 1

[为了更容易理解，我们可以用等式伪代码编写它，同时我们使用Monad Comprehensions来简化和定义，以替代和简化定义。

Monad推导与列表推导一样，仅适用于任何MonadPlus类型，而不仅适用于[]；而与do表示法非常接近，例如[ (f a, s') | (a, s') <- parse p s ] === do { (a, s') <- parse p s ; return (f a, s') }。

这使我们：

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

instance Functor Parser where
   parse (fmap f p)  s  =  [ (f a, s') | (a, s') <- parse p s ]

instance Applicative Parser where
   parse (pure a)    s  =  pure (a, s)
   parse (pf <*> pa) s  =  [ (g a, s'') | (g, s')  <- parse pf s 
                                        , (a, s'') <- parse pa s' ]

instance Alternative Parser where
   parse empty s      =  empty
   parse (l <|> r) s  =  parse l s <|> parse r s

ensure :: (a -> Bool) -> Parser a -> Parser a
parse (ensure pred p) s  =  [ (a, s') | (a, s') <- parse p s, pred a ]

lookahead :: Parser (Maybe Char)
parse lookahead []       =  pure (Nothing, [])
parse lookahead s@(c:_)  =  pure (Just c,  s )

satisfy :: (Char -> Bool) -> Parser Char
parse (satisfy p) []      =  mzero
parse (satisfy p) (x:xs)  =  [ (x, xs) | p x ]

eof :: Parser ()
parse eof s  =  [ ((), []) | null s ]  

eof' :: Parser ()
eof'  =  ???

通过使用Monad Comprehensions和更抽象的pure，empty和mzero，而不是根据Maybe类型的具体表示，此相同的（伪）代码将起作用具有不同类型，例如[]代替Maybe，即。 newtype Parser a = Parser { parse :: String -> [(a,String)] }。

所以我们有

ensure    :: (a -> Bool) -> Parser a           -> Parser a
lookahead ::                Parser (Maybe Char)

_{（[satisfy在这里对我们没有好处...。为什么？）}

使用它，我们可以拥有

ensure  .......  ......                        :: Parser (Maybe Char)

_{（... ensure id (pure False)做什么？...）}

但是在输入字符串实际上为空的情况下，我们将得到无用的Nothing结果，而在这种情况下，为使用而提供的eof解析器将生成()作为其结果（否则将不产生任何结果） 。

不用担心，我们也有

fmap :: (  a      ->   b )                     -> Parser a        ->  Parser b

可以为我们将Nothing转换为()。我们需要一个始终为我们做到这一点的功能，

alwaysUnit nothing  =  ()

我们现在可以使用它来得出解决方案：

eof'  =  fmap ..... (..... ..... ......)