many1 turns a parser p into a parser for one or more consecutive occurrences of p. Its result is a List of the values produced by those occurrences. The crucial distinction from many is the lower bound: many may succeed with an empty list, while many1 must first obtain one successful result. section 9.2.1 section 9.8
The need appears whenever an empty match would accept too much input. A parser for one or more 'a' characters uses char('a').many1; this can then be sequenced after a parser for zero or more 'a' characters to recognize zero or more a values followed by one or more b values. The first required match makes the second region genuinely nonempty. section 9.2.1
many1 need not be primitive. It is p followed by p.many: run p once, run the zero-or-more parser on the remaining input, and combine the head value with the remaining list. product supplies sequencing, and map2 transforms the paired results into the desired List. section 9.2.1 section 9.8
extension [A](p: Parser[A])
def many1: Parser[List[A]] =
p.map2(p.many)(_ :: _)
This definition makes the nonempty result explicit: _ :: _ places the mandatory first parse result at the front of the list returned by many. section 9.8
Building a nonempty repetition parser
Given p: Parser[A], define many1 with p.map2(p.many)(_ :: _). If p parses its first value successfully, many parses every additional successful occurrence and may contribute Nil. Consing the first value onto that tail means a successful many1 result always contains at least one element. section 9.8 section 9.8
When implementing or reasoning about many1, separate these responsibilities:
- Require the initial p parse to succeed; unlike many, do not provide succeed(Nil) as an alternative for the whole combinator. section 9.2.1 section 9.8
- Use map2 to sequence p with p.many and construct the result list with cons. section 9.8
- Keep the recursive implementation of many deferred or nonstrict: a strict recursive map2 argument can overflow the stack while constructing many. section 9.8
This small combinator illustrates algebraic API design: choose a few operations for sequencing, alternatives, successful values, and mapping, then derive reusable combinators from them. many1 is a direct reuse of many and map2 rather than a separate parsing mechanism. section 9.2.1 section 9.8
