Unable to understand a mutual recursion

Question

I am reading 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 permits zero or more applications of p, whereas 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 the recursive call happens at

vs <- many p

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

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

Answer 1

The recursion stops at the v <- p line. The monadic behavior of the Parser will just propagate a [] to the end of the computation when p cannot be parsed anymore.

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

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

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

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