Search code examples
parsinghaskellparser-combinators

Understanding Text.ParserCombinators.ReadP.sepBy1

I am confused by the result of sepBy1

Following code is running in ghci

λ> import Text.ParserCombinators.ReadP
λ> import Data.Char

λ> readP_to_S ((munch1 isAlpha) `sepBy1` (char '-')) "dish-dash-dosh"
[(["dish"],"-dash-dosh"),(["dish","dash"],"-dosh"),["dish","dash","dosh"],"")]
  1. Why it is not the case that output is [(["dish","dash","dosh"],"")]?

The following doctest is only one that failed.

-- |
-- >>> readP_to_S readValues "dish-dash-dosh"
-- [(V ["dish","dash","dosh"],"")
readValues :: ReadP Value
readValues = do
  xs <- (munch isAlpha) `sepBy1` (char '-')
  pure $ V xs

Main.hs:64: failure in expression `readP_to_S readValues "dish-dash-dosh"'
expected: [(V ["dish","dash","dosh"],"")
 but got: [(V ["dish"],"-dash-dosh"),(V ["dish","dash"],"-dosh"),(V ["dish","dash","dosh"],"")]

I am using ReadP for Read instance of my data. The code for Read instance is working but I am confused.

Haven't done any complex parsing, I always think that running ReadP will return output in form of single element list [(result,"")], obviously it is not the case.

data Value = V [String]
  deriving Show

-- |
-- >>> read "dish-dash-dosh" :: Value
-- V ["dish","dash","dosh"]
--
instance Read Value where
  readPrec = readP_to_Prec (const readValues)
  1. Is it the case that read will success only if there is nothing left in the snd of the last [(Value,String)], other elements in this list are unuse anywhere?

I am aware of alternative way to do this. This question is solely about understanding sepBy output and it usage.

Solution

  • Running ReadP will return all the possible parses. You can restrict the number of valid parses by specifying what should happen after the sepBy1 parse, e.g. end of input or some other syntactic element.

    For instance, try something like:

    readValues = do
  xs <- (munch isAlpha) `sepBy1` (char '-')
  eof
  pure $ V xs

    Addendum...

    The ReadS type follows the development of monadic parsing as presented in the classic Hutton and Meijer paper Monadic Parsing in Haskell. From the little documentation there is, I gather that the ReadP implements parallel exploration of all alternatives. There is a lot of support for creating ReadP actions and not so much for ReadS, so I think you're using the library correctly by building a ReadP action and then using readP_to_S at the end. When I've used the module I've just taken the first match of the ReadS action (or returned a parse error if it was the empty list.)

    The ReadPrec monad is used to support precedence, and it basically is ReaderT Int ReadP -- here the Int is the current precedence. Again, it looks like you start with a ReadP parser and then convert it to a ReadPrec action using lift or readP_to_Prec. To run it you can use readPrec_to_S just like in the ReadP case.