#8924: Text.ParserCombinators.ReadP needs some kind of "commit" or "cut" to force a single parse.. -------------------------------------+------------------------------------ Reporter: PaulJohnson | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.6.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: None/Unknown | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Changes (by simonpj): * cc: koen@… (added) Old description:

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.

New description: 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. -- Comment: Adding Koen, who wrote this library. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8924#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler