Implementing (<++) within a Haskell Parser

Question

The goal of this is to implement <++ in Haskell using StateT to act as a parser

    import Control.Monad.State

    type Parser = StateT String []

    runParser :: Parser a -> String -> [(a,String)]
    runParser = runStateT

    parser :: (String -> [(a,String)]) -> Parser a
    parser = StateT

    (<++) :: Parser a -> Parser a -> Parser a

From this base, how could I implement <++ so that it mirrors the definition in Text.ParserCombinators.ReadP

Local, exclusive, left-biased choice: If left parser locally produces any result at all, then right parser is not used.

Not sure how to address the problem. I'm not sure how to apply priority to the first parser so that if it succeeds the program does not go onto check the second parser. And then upon failure have the code check the second parser. If i simply wanted to combine the two parsers I could use mplus or msum, but I'm not sure how to then reduce that to only return 1 value. I'm not sure how to approach this. — Kayanda
– Kayanda, Commented Nov 16, 2016 at 5:59
an empty list correct, but the issue is that If both parsers succeed and are combined I get both results. In this case I only want the first parser if it succeeds. If the first or second one fails, then (<++) is equivalent to mplus. If the both succeed then they are no longer equivalent. How should I address this case — Kayanda
– Kayanda, Commented Nov 16, 2016 at 6:09
the definition of <++ is that it takes two parser and returns a new parser. Because of this I can't runParser along with the initial state to see what i get. If you meant something different from this could you further explain it. — Kayanda
– Kayanda, Commented Nov 16, 2016 at 6:20

ase · Accepted Answer · 2016-11-16 11:08:31Z

3

Your parser are functions String -> [(a,String)] where the argument is the initial state. So lets construct such a function that tries the first parser, and if it fails tries the second parser:

(<++) :: Parser a -> Parser a -> Parser a
p1 <++ p2 =
  parser $ \s0 ->            -- 1. captures initial state
    case runParser p1 s0 of  -- 2. run first parser
      (x:xs) -> x : xs       -- 3. success
      [] -> runParser p2 s0  -- 4. otherwise run second parser

Some parsers to try this out

-- | Always fails
failP :: Parser a
failP = parser (const [])

-- | Parses an Int
intP :: Parser Int
intP = parser reads

Output as expected? (Perhaps there are more enlightening test cases...)

λ> runParser (failP <++ intP) "2014"
[(2014,"")]
λ> runParser (intP <++ failP) "2014"
[(2014,"")]
λ> runParser (intP <++ intP) "2014"
[(2014,"")]

answered Nov 16, 2016 at 11:08

ase

13.6k4 gold badges37 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Kayanda Over a year ago

Thank you, I tried a similar method, but forgot to wrap the lambda function in parser so the type check failed. This makes total sense now.

ase Over a year ago

@Kayanda it is customary on Stackoverflow to mark an answer as accepted using the checkmark beside the score if that answer is sufficient.

Collectives™ on Stack Overflow

Implementing (<++) within a Haskell Parser

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related