[GHC] #8924: Text.ParserCombinators.ReadP needs some kind of "commit" or "cut" to force a single parse..

23 Mar 2014

      #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
       Keywords:                    |  Operating System:  Unknown/Multiple
   Architecture:  Unknown/Multiple  |   Type of failure:  None/Unknown
     Difficulty:  Unknown           |         Test Case:
     Blocked By:                    |          Blocking:
Related Tickets:                    |
------------------------------------+-------------------------------------
 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.

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8924
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler