Haskell Parser not working

Question

I am trying to understand Parsers. Therefore I have created my own parser. Unfortunately it does not work. Why?

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

preturn :: a -> Parser a 
preturn t = \inp -> [(t,inp)] 

pfailure :: Parser a 
pfailure = \inp -> []

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


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

parse p inp = p inp

{-
combine :: Parser a -> Parser b -> Parser (a,b)
combine p1 p2 = \inp -> p2 t output
    where
        p1 inp = ([


-}
-- firstlast :: Parser (Char,Char)
firstlast = do 
    x <- pitem
    z <- pitem
    y <- pitem
    preturn (x,y)

another = do
    x <- pitem
    y <- pitem

Firstlast is supposed to take a string and return the first and third character. Unfortunately, it returns odd values, and it does not accept its type (Parser (Char,Char))

For example,

*Main> firstlast "abc"
[(([('a',"bc")],[('a',"bc")]),"abc")]

What should happen is:

*Main> firstlast "abc"
[("ac",[])]

Answer 1

Please use code that compiles. Your another function does not.

What's the problem?

Your code for firstlast and another makes use of do-notation. And the way you're using pitem here, it looks as if you're expecting Parser to be a monad. But it isn't, at least not in the way you expect it to be.

There is a monad instance pre-defined which make GHC think that Parser is a monad, namely

instance Monad ((->) r) where
  return = const
  f >>= k = \ r -> k (f r) r

What this instance says is that, for any type r the function type r -> ... can be considered a monad, namely by distributing the parameter everywhere. So returning something in this monad amounts to producing a value ignoring the parameter of type r, and binding a value means that you take r and pass it on both to the left and right computation.

This is not what you want for a parser. The input string will be distributed to all computations. So each pitem will operate on the original input string. Furthermore, as

pitem :: String -> [(Char, String)]

the result of your monadic computation will be of type [(Char, String)], so x and y are both of this type. That's why you get the result

[(([('a',"bc")],[('a',"bc")]),"abc")]

You're calling pitem three times on the same input string. You're putting two results in a pair, and you're preturn-ing the whole thing.

How to fix it?

You need to define your own monad instance for the Parser type. You cannot do that directly, because Parser is a type synonym, and type synonyms cannot be partially applied, so you cannot write

instance Monad Parser where
  ...

Instead, you have to wrap Parser in a new datatype or newtype:

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

This gives you a constructor Parser and a function parse to convert between the unwrapped and wrapped parser types:

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

This implies you'll have to adapt your other functions. For example, preturn becomes

preturn :: a -> Parser a 
preturn t = Parser (\inp -> [(t,inp)])

Change pfailure and pitem similarly. Then, you have to define the Monad instance:

instance Monad Parser where
  return = preturn
  (>>=)  = ... -- to be completed by you

The function (>>=) is not contained in your code above. You'll want to implement the behaviour that the input is passed to the first parser, and for every result of that, the result and the remaining input are passed to the second argument of (>>=). Once this is done, a call to parse firstlast "abc" will have the following result:

[(('a','c'),"")]

which isn't quite what you want in your question, but I believe it's what you're actually after.