Чтобы понять это проще, мы можем записать его в эквациональном псевдокоде, в то время как мы подставляем и упрощаем определения, используя Монадные Постижения для ясности и краткости.
Монадные Постижения аналогичны Постижиманиям Списка, работают только для любого типа 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 ..... (..... ..... ......)