Why am I getting a type error in this sequence of parsers (lecture 8 by Erik Meijer)?

Question

I'm in the process of watching the Functional Programming Fundamentals lecture series by Erik Meijer (with slides by Graham Hutton).

In lecture 8 (on functional parsers), after defining the Parser a type, introducing a few parsing primitives (including item and return, which I named return'), Erik gives a simple example of how his parsers can be combined in a sequence, using the do syntax:

type Parser a = String -> [(a,String)]

item :: Parser Char                                                  
item = \inp -> case inp of                                                   
                 []     -> []                                             
                 (x:xs) -> [(x,xs)]

return' :: a -> Parser a                                                   
return' v = \inp -> [(v,inp)]

p :: Parser (Char,Char)
p = do x <- item
       item
       y <- item
       return' (x,y)

However, when I try to load this in GHCi, I get the following type error, which I didn't expect and don't understand:

Couldn't match type ‘[(Char, String)]’ with ‘Char’
Expected type: String -> [((Char, Char), String)]
  Actual type: Parser ([(Char, String)], [(Char, String)])
In a stmt of a 'do' block: return' (x, y)
In the expression:
  do { x <- item;
       item;
       y <- item;
       return' (x, y) }
Failed, modules loaded: none.

What am I doing wrong?

Answer 1

This error message is a little bit confusing because GHC unpacked your Parser type into its definition of String -> [(a, String)]. If we undo this transformation, it'll start making a bit more sense:

Expected type: Parser (Char, Char)
  Actual type: Parser ([(Char, String)], [(Char, String)])

Now it's starting to make a bit more sense. What it looks like is that you took the result of two calls to a Parser Char (ie [(Char, String)]) and then used them as if they were normal Chars. The error happens at line 15, which is your call to return':

return' (x, y)

This tells us that x and y are the two problematic results.

The do block you have is using the monad instance for functions of the type String -> b; what this does is combine them into a larger function of String -> b by stringing the input (String) through all of the functions. A line like x <- item lets you get the b element from the String -> b function while maintaining all the plumbing to pass the String argument through. Unfortunately, item is a Parser Char, which means the b is actually a [(Char, String)] and not just a Char.

This extra returned structure is needed to parse correctly. The String represents the rest of the input that was not consumed to parse the Char (or whatever you're parsing) and the whole thing is a list because there can be multiple possible ways to validly parse part of the input which all need to be handled.

To make this work, you have to have some way to take care of this extra structure. However, since I haven't followed the course or watched the lecture, I don't know what it is. You could define your own monad instance instead of relying on the built-in instance for functions, but you might not have gotten far enough into the class to do this yourself, or Meijer might be using a non-standard library to avoid this issue, in which case you need to make sure your setup matches what the class expects.

Answer 2

The problem is that the do notation in your definition of p is not using the monad you want it to use.

I could be wrong, but it looks like p is using a version of the Reader monad.

If you use this definition you'll see that x and y are not Char values but have type [(Char,String)]:

import Debug.Trace

p :: Parser (Char,Char)
p = do x <- item
       y <- item
       let foo = trace ("x = " ++ show x) 'a'
           bar = trace ("y = " ++ show y) 'b'
       return' (foo,bar)

test = p "qwe"

If you want to use do notation, you should create a newtype or data declaration for Parser so you can define how the bind operator (>>=) works, e.g.:

newtype Parser a = Parser { parse :: String -> [ (a,String) ] }

instance Monad Parser where
    return   = Parser . return'
    (>>=)    = ...

Here is a good blog post on how to define a parser monad instance using newtype: (link)