Объединение парсеров в 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 / Альтернативные примеры выше. Я застрял на этом, поскольку у меня нет опыта в комбинировании парсеров. Может кто-нибудь мне помочь ?

Answer 1

Чтобы понять это проще, мы можем записать его в эквациональном псевдокоде, в то время как мы подставляем и упрощаем определения, используя Монадные Постижения для ясности и краткости.

Монадные Постижения аналогичны Постижиманиям Списка, работают только для любого типа 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 (<b>fmap f p</b>)  s  =  [ (f a, s') | (a, s') <- parse p s ]

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

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

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

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

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

eof :: Parser ()
parse <b>eof</b> s  =  [ ((), []) | null s ]  

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

Кстати, благодаря использованию Пониманий Монады и более абстрактным 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 ..... (..... ..... ......)