Unable to understand mutual recursion

Question

I read "Programming in Haskell", in the 8th chapter the author gives an example of writing parsers. The full source is here: http://www.cs.nott.ac.uk/~gmh/Parsing.lhs I can’t understand the following part: many resolves zero or more applications p , while many1 requires at least one successful application:

 many :: Parser a → Parser [a ] many p = many1 p +++ return [ ] many1 :: Parser a → Parser [a ] many1 p = do v ← p vs ← many p return (v : vs) 

How does a recursive call occur when

 vs <- many p 

vs is the result of the result of many p , but many p, called many1 p , all many1 have a notation in their definition and again have the value of the result v and vs when the recursive call returns? Why can the following snippet return [("123","abc")] ?

 > parse (many digit) "123abc" [("123", "abc")] 

Answer 1

For the last question:

 > parse (many digit) "123abc" [("123", "abc")] 

Means the parsing was successful because at least one result was returned in the answer list. Hutton guerrillas always return a list - an empty list means parsing.

The result (“123”, “abc”) means that the parsing detected three digits “123” and stopped at “a”, which is not a digit, so “the rest of the input” is “abc”.

Note that many means "as much as possible" not "one or more." If it were "one or more", you would get this result:

 [("1", "23abc"), ("12", "3abc"), ("123", "abc")] 

This behavior is not well suited for deterministic parsing, although sometimes it may be required for natural language parsing.

Answer 2

Recursion stops at v <- p . Parser's monadic behavior will simply propagate [] until the end of the calculation when p no longer processed.

 p >>= f = P (\inp -> case parse p inp of [] -> [] -- this line here does not call f [(v,out)] -> parse (fv) out) 

The second function is written in do-notation, which is just good syntax for the following:

 many1 p = p >>= (\v -> many p >>= (\vs -> return (v : vs))) 

If parsing p causes an empty list [] , the function \v -> many p >>= (\vs -> return (v : vs)) will not be called, stopping the recursion.

Answer 3

Let me take this to the simplest of bones so that it is completely clear why do blocks can be misunderstood if they are read simply as imperative code. Consider this snippet:

 doStuff :: Maybe Int doStuff = do a <- Nothing doStuff 

It seems that doStuff will return forever, in the end, he determined the sequence of things ending in doStuff . But the sequence of lines in the do block is not just a sequence of operations that are performed in order. If you are at the do block point, then the definition of >>= is determined by how the rest of the block is processed. In my example, the second argument >>= used only if the first argument is Nothing . Therefore, recursion never happens.

Something similar can happen in many different monads. Your example is a bit more complicated: when there are no more ways to parse, the material after >>= ignored.