Opened 19 months ago

Last modified 19 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: Compiler Version: 7.6.3
Keywords: Cc: koen@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):

Description (last modified by simonpj)

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 (1)

comment:1 Changed 19 months ago by simonpj

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

Adding Koen, who wrote this library.

Note: See TracTickets for help on using tickets.