Соответствующий совет: Не паникуйте (имеется в виду, не торопите его или не торопитесь) и Следуйте указаниям .
Прежде всего, Parser s
type Parser a = String -> [(a,String)]
являются функциями от String до списков пар значений результата типа a и оставшихся строк.Эта строка остатки будет использоваться в качестве input для следующего шага синтаксического анализа.Это главное здесь.
Вы спрашиваете, в
p >>= f = \inp -> case (parse p inp) of
[] -> []
[(v,out)] -> parse (f v) out
, как (f v) в [(v,out)] -> parse (f v) out возвращает синтаксический анализатор, который затем применяется к out?
Ответ: f ' type говорит, что это так:
(>>=) :: Parser a -> (a -> Parser b) -> Parser b -- or, the equivalent
(>>=) :: Parser a -> (a -> Parser b) -> (String -> [(b,String)])
-- p f inp
У нас есть f :: a -> Parser b, так что этотолько то, что он делает: применительно к значению типа a возвращает значение типа Parser b.Или, что эквивалентно,
f :: a -> (String -> [(b,String)]) -- so that
f (v :: a) :: String -> [(b,String)] -- and,
f (v :: a) (out :: String) :: [(b,String)]
Так что, независимо от значения, которое parse p inp производит , оно должно быть тем, что f ожидает для продолжения.Типы должны «соответствовать» :
p :: Parser a -- m a
f :: a -> Parser b -- a -> m b
f <$> p :: Parser ( Parser b ) -- m ( m b )
p >>= f :: Parser b -- m b
или, что эквивалентно,
p :: String -> [(a, String)]
-- inp v out
f :: a -> String -> [(b, String)]
-- v out
p >>= f :: String -> [(b, String)] -- a combined Parser
-- inp v2 out2
Так что это также отвечает на ваш второй вопрос,
Как это может быть парсером и как он может принимать out в качестве аргумента?
Реальный вопрос в том, что это за f, что делает такое?Откуда это взялось?И это ваш четвертый вопрос.
И ответ таков: ваш пример в do -обозначении,
p :: Parser (Char, Char)
p = do x <- item
_ <- item
y <- item
return (x,y)
по законам Монады эквивалентен вложенной цепочке
p = do { x <- item
; do { _ <- item
; do { y <- item
; return (x,y) }}}
, который является синтаксическим сахаром для вложенной цепочки Parser bind приложений,
p :: Parser (Char, Char) -- ~ String -> [((Char,Char), String)]
p = item >>= (\ x -> -- item :: Parser Char ~ String -> [(Char,String)]
item >>= (\ _ -> -- x :: Char
item >>= (\ y -> -- y :: Char
return (x,y) )))
, и это , потому что функции вложены, чтофинал return имеет доступ к и y и x там;и именно Parser bind обеспечивает вывод строки остатков для использования в качестве входных данных для следующего шага синтаксического анализа:
p = item >>= f -- :: String -> [((Char,Char), String)]
where
{ f x = item >>= f2
where { f2 _ = item >>= f3
where { f3 y = return (x,y) }}}
, т. е. (при условии, что inp - это строка длиной два или более),
parse p inp -- assume that `inp`'s
= (item >>= f) inp -- length is at least 2 NB.
=
let [(v, left)] = item inp -- by the def of >>=
in
(f v) left
=
let [(v, left)] = item inp
in
let x = v -- inline the definition of `f`
in (item >>= f2) left
=
let [(v, left)] = item inp
in let x = v
in let [(v2, left2)] = item left -- by the def of >>=, again
in (f2 v2) left2
=
..........
=
let [(x,left1)] = item inp -- x <- item
[(_,left2)] = item left1 -- _ <- item
[(y,left3)] = item left2 -- y <- item
in
[((x,y), left3)]
=
let (x:left1) = inp -- inline the definition
(_:left2) = left1 -- of `item`
(y:left3) = left2
in
[((x,y), left3)]
=
let (x:_:y:left3) = inp
in
[((x,y), left3)]
после нескольких упрощений.
И это отвечает на ваш третий вопрос.