# [Haskell-cafe] [Parsec] A combinator to match between M and N times?

Robert Dockins robdockins at fastmail.fm
Tue Aug 29 10:35:58 EDT 2006

On Aug 29, 2006, at 9:11 AM, Tomasz Zielonka wrote:

> On Tue, Aug 29, 2006 at 03:05:39PM +0200, Stephane Bortzmeyer wrote:
>> Parsec provides "count n p" to run the parser p exactly n times. I'm
>> looking for a combinator "countBetween m n p" which will run the
>> parser between m and n times. It does not exist in Parsec.
>
>> Much to my surprise, it seems quite difficult to write it myself and,
>> until now, I failed (the best result I had was with the "option"
>> combinator, which unfortunately requires a dummy value, returned when
>> the parser fails).
>
>
>     countBetween m n p = do
>         xs <- count m p
>         ys <- count (n - m) \$ option Nothing \$ do
>             y <- p
>             return (Just y)
>         return (xs ++ catMaybes ys)
>
> Assuming n >= m.
>
>> Does anyone has a solution? Preferrably one I can understand, which
>> means not yet with liftM :-)
>
> No liftM, as requested :-)

Here's an interesting puzzle.  For a moment, consider parsec only wrt
its language-recognition capabilities.

Then, we expect the count combinator to factor,

count x p >> count y p === count (x+y) p

where === mean "accepts the same set of strings".

I somehow intuitively expect the countBetween combinator to factor in
a similar way also, but it doesn't (at least, none of the posted
versions do)!  Note the output of:

parser1 = countBetween 3 7 (char 'a') >> eof
parser2 = countBetween 2 3 (char 'a') >> countBetween 1 4 (char 'a')
>> eof

main = do
print \$ parse parser1 "" "aaa"
print \$ parse parser2 "" "aaa"

OK.  What's happening is that the greedy nature of the combinator
breaks things because parsec doesn't do backtracking by default.  I'd
expect to be able to insert 'try' in the right places to make it
work.  However, after playing around for a few minutes, I can't
figure out any combination that does it.  Is it possible to write
this combinator so that it factors in this way?

> Best regards
> Tomasz

Rob Dockins

Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
-- TMBG