Monadic parsing functional pearl - gluing multiple parsers together

haskell, parsing

Solution

I'll try shedding some more light regarding `>>`. As you see in the other answer, you should desugar the do's into `>>=` to better understand what's going on.

Let's for example write a parser that parses two chars and returns them.

twoChars :: Parser (Char,Char)
twoChars = do
  i <- item
  j <- item
  return (i,j)

Now, desugar the `do` syntax:

twoChars :: Parser (Char,Char)
twoChars =
  item >>= (\i ->
  item >>= (\j ->
  return (i,j) ) )

I put brackets for clarity. As you see, the second `item` receives the result of the first `item` parser in the anonymous function, with the result bound to `i`. The `>>=` function takes a parser, a function, and returns a parser. Best way to understand it would be to plug it into the definition:

f = \i → item »= \j → return (i,j)
twoChars = item >>= f
twoChars = Parser (\cs -> concat [parse (f a) cs' | (a,cs') <- parse item cs])

So we got back a new Parser. Try to imagine what it will do on an input "abc". `cs` is bound to "abc", and the item Parser is used to get back [('a',"bc")]. Now, we apply `f` to 'a', to get back the new parser:

item >>= \j -> return ('a',j)

This parser will be passed the rest of our string left to process (`"bc"`), and it will use the `item` parser to get out the `b` when the `\j` above is bound to `b`. We then get a `return ('a','b')` statement, which puts `('a','b')` into a parser that just return `('a','b')`.

I hope this clears up how the information flow happens. Now, suppose that you want to ignore a character. You could do it like this.

twoChars :: Parser (Char,Char)
twoChars =
  item >>= \i ->
  item >>= \j ->
  item >>= \k ->
  return (i,k)

It's ok that the `j` is bound to `'b'` for the example "abc", you never use it. We can so replace `j` by `_`.

twoChars :: Parser (Char,Char)
twoChars =
  item >>= \i ->
  item >>= \_ ->
  item >>= \k ->
  return (i,k)

But we also know that `>> :: m a -> m b -> m b` can be defined as:

p >> q = p >>= \_ -> q

So we are left with

twoChars :: Parser (Char,Char)
twoChars =
  item >>= \i ->
  item >>
  item >>= \k ->
  return (i,k)

Finally, you can sugar this back into `do`. The application of `>>` simply sugars into a single-line statement with no bounding. It results in:

twoChars :: Parser (Char,Char)
twoChars = do
  i <- item
  item
  j <- item
  return (i,j)

Hope this cleared some things up.

Problem

I am working my way through the functional pearl paper `Monadic parsing in Haskell` (after recommendation at `haskellforall.com` to read that paper to understand parsing). I wrote an implementation until section 4 on page 3 as below: ``` newtype Parser a = Parser (String -> [(a,String)]) parse (Parser p) = p instance Monad Parser where return a = Parser (\cs -> [(a,cs)]) p >>= f = Parser (\cs -> concat [parse (f a) cs' | (a,cs') <- parse p cs]) item :: Parser Char item = Parser (\cs -> case cs of "" -> [] (c:cs) -> [(c,cs)]) p :: Parser (Char,Char) p = do { a <- item; item; b <- item; return (a,b)} ``` According to the paper, `p` is a parser that consumes three characters, skips middle one, and returns a pair of first and second. What I can't figure out is how the modified input string is passed to 2nd and 3rd definitions of `item` in `p`. We are not passing the result of first parser to second parser, and so on (because `;`, syntactic sugar for `>>` is used which discards the result as shown by type signature `(>>) :: Monad m => m a -> m b -> m b`). I will appreciate explanation of how the modified function is being passed in last two invocations of `item` in `p`. Another thing that confuses me is the handling of `cs` in `item` - it doesn't return (head,tail) pair. Shouldn't it be redefined as follow since the `item` parser consumes one character according to the paper: ``` item :: Parser Char item = Parser (\cs -> case cs of "" -> [] (c:cs') -> [(c,cs')]) -- redefinition - use cs' to denote tail ```

Original source