Haskell Type Error

Question

Consider the following piece of Haskell code:

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

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

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

 parse :: Parser a -> String -> [(a, String)]
 parse p inp = p inp

 pseq :: Parser (Char, Char)
 pseq = do x <- item
           item
           y <- item
           ret (x, y)

 ac = parse pseq "abcdef"

When trying to run the above code in hugs (Version September 2006), I get the following error message:

Type error in explicitly typed binding
*** Term           : pseq
*** Type           : [Char] -> [(([(Char,[Char])],[(Char,[Char])]),[Char])]
*** Does not match : Parser (Char,Char)

And, when I remove my type declaration for "pseq", I get the following error message:

Unresolved top-level overloading
*** Binding             : pseq
*** Outstanding context : Monad ((->) [Char])

Answer 1

The problem is that you're trying to use do-notation for Parser, but it's not exactly a Monad. It is sort of, because there's a Monad instance for r ->, but that makes the type on the right-hand side of the -> the "element" type of the Monad, and here you want the element type to be the a in [(a,String)]. You need to make the definition of Parser a newtype, and write a custom Monad instance for it (or compose it out of exising monads/transformers like ListT and StateT).

Answer 2

Making Parser a Monad is easy, and I think resorting to ListT or StateT is probably overkill here.

newtype Parser a = Parser (String -> [(a, String)])
    -- make this a distinct type
    -- now the function is "wrapped", though at no run-time cost

instance Monad Parser where
    return = ret    -- you already had it defined
    (>>=) = bind    -- added below
    -- this instance makes Parser a Moand, and lets it work with do notation

item :: Parser Char
item = Parser $ \ inp -> case inp of
                         [] -> []
                         (x:xs) -> [(x, xs)]
    -- need to "wrap" up the function as a Parser value

ret :: a -> Parser a
ret v = Parser $ \ inp -> [(v, inp)]
    -- need to "wrap" up the function as a Parser value

bind :: Parser a -> (a -> Parser b) -> Parser b
bind p f = Parser $ \ s -> case parse p s of
                           [] -> []
                           [(a, s')] -> parse (f a) s'
    -- the only function you were missing
    -- it is worth making sure you understand how it works

parse :: Parser a -> String -> [(a, String)]
parse (Parser p) inp = p inp
    -- needs to "unwrap" the newtype here

pseq :: Parser (Char, Char)
pseq = do x <- item
          item
          y <- item
          ret (x, y)

ac = parse pseq "abcdef"
    -- you probably meant pseq here, not seq

Lastly, you use the return type of [(a, String)], so that you can indicate things which can't parse. But the list only ever has zero or one items in it. You should look into the types Maybe and Either which would likely be clearer in this case.