无法理解相互递归

Question

我正在阅读在Haskell编程,在第8章中,作者给出了编写解析器的示例.完整的来源是:http://www.cs.nott.ac.uk/~gmh/Parsing.lhs 我无法理解以下部分:many 允许零个或多个应用程序p,但many1需要至少一个成功的应用程序:

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)

递归调用是如何发生的

vs <- many p

vs是结果值many p,但很多p调用many1 p,many1在它的定义中都有一个do表示法,并且还有结果值v,并且vs,递归调用何时返回？为什么以下代码段可以返回[("123","abc")]？

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

Answer 1

递归在该v <- p行停止.[]当p无法解析时,解析器的monadic行为将只传播到计算的结尾.

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

第二个函数是用do-notation编写的,这对于以下内容来说只是一个很好的语法:

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

如果解析p产生一个空列表[],\v -> many p >>= (\vs -> return (v : vs))则不会调用该函数,从而停止递归.