Opened 4 years ago

Last modified 20 months ago

#8924 new feature request

Text.ParserCombinators.ReadP needs some kind of "commit" or "cut" to force a single parse..

Reported by: PaulJohnson Owned by:
Priority: normal Milestone:
Component: Core Libraries Version: 7.6.3
Keywords: Cc: koen@…, ekmett
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by thomie)

The ReadP monad maintains all possible parses of its input, rather than being left-biased as most parsers are. However this is not always quite the Right Thing. I maintain the Data.Decimal library. The Read instance for Data.Decimal up to 0.3.1 had the following behaviour:

    reads "34.567e8 foo" :: [(Decimal, String)] = [(34.0,".567e8 foo"),(34.567,"e8 foo"),(3.4567e9," foo")]

Clearly only the last parse in the list is the Right Thing, and any parser which returns "34.0" when given "34.567" is doing it wrong.

The problem came from the implementation of "optional". In numbers only the integer part is mandatory, with the fractional and exponent parts being optional. So I wrote my parser with the fractional part parsed like this:

          fractPart    <- optional "" $ do
                            _ <- char '.'
                            munch1 isDigit

The problem is that "optional" uses the symmetric choice operator (+++). I wrote this to work around the problem:

    myOpt d p = p <++ return d

This uses the left-biased choice, so as soon as the parser sees the "." it commits to the fractional part.

However this still isn't the Right Thing.

    reads "34." :: [(Double, String)] = [(34.0, ".")]

but the parser above will fail to read it. Furthermore there are a number of combinators built on "+++" in ReadP, and it seems wrong to have left-biased variants of all of them.

So what seems to be needed is some kind of "cut" operator, analogous to the Prolog "!" cut, which says that if you have got this far then you should commit to this parse and forget all the others. But it would have to be delimited because I only want that cut to apply to my Decimal type: if someone calls my Decimal parser then I don't want their parser to commit to an entire parse just because I have.

So I think the feature I'm looking for is a delimited back-track akin to "prompt" in delimited continuations. But my monad-fu isn't good enough to design it.

Change History (2)

comment:1 Changed 3 years ago by simonpj

Cc: koen@… added
Description: modified (diff)

Adding Koen, who wrote this library.

comment:2 Changed 20 months ago by thomie

Cc: ekmett added
Component: CompilerCore Libraries
Description: modified (diff)

my monad-fu isn't good enough to design it.

It's two year later, maybe your monad-fu is good enough to design it now? See WorkingConventions/AddingFeatures for how to submit a patch.

Or maybe the CLC has something to say about this feature request?

Note: See TracTickets for help on using tickets.