Foldl-like operator for Parsec

user_7095230 0
Viewed 67

Suppose I have a function of this type:

once :: (a, b) -> Parser (a, b)

Now, I would like to repeatedly apply this parser (somewhat like using >>=) and use its last output to feed it in the next iteration.

Using something like

sequence :: (a, b) -> Parser (a, b)
sequence inp = once inp >>= sequence

with specifying the initial values for the first parser doesn't work, because it would go on until it inevitably fails. Instead, I would like it to stop when it would fail (somewhat like many).

Trying to fix it using try makes the computation too complex (adding try in each iteration).

sequence :: (a, b) -> Parser (a, b)
sequence inp = try (once inp >>= sequence) <|> pure inp

In other words, I am looking for a function somewhat similar to foldl on Parsers, which stops when the next Parser would fail.

parsec haskell
1 Answers

If your once parser fails immediately without consuming input, you don't need try. As a concrete example, consider a rather silly once parser that uses a pair of delimiters to parse the next pair of delimiters:

once :: (Char, Char) -> Parser (Char, Char)
once (c1, c2) = (,) <$ char c1 <*> anyChar <*> anyChar <* char c2

You can parse a nested sequence using:

onces :: (Char, Char) -> Parser (Char, Char)
onces inp = (once inp >>= onces) <|> pure inp

which works fine:

> parseTest (onces ('(',')')) "([])[{}]{xy}xabyDONE"
('a','b')

You only need try if your once might fail after parsing input. For example, the following won't parse without try:

> parseTest (onces ('(',')')) "([])[not valid]"
parse error at (line 1, column 8):
unexpected "t"
expecting "]"

because we start parsing the opening delimiter [ before discovering not valid].

(With try, it returns the correct ('[',']').)

All that being said, I have no idea how you came to the conclusion that using try makes the computation "too complex". If you are just guessing from something you've read about try being potentially inefficient, then you've misunderstood. try can cause problems if it's used in a manner than can result in a big cascade of backtracking. That's not a problem here -- at most, you're backtracking a single once, so don't worry about it.

user_72030160
Related