Two classes ago, our professor presented to us a Parser module.

Here is the code:

module Parser (Parser,parser,runParser,satisfy,char,string,many,many1,(+++)) where

import Data.Char
import Control.Monad
import Control.Monad.State

type Parser = StateT String []

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

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

satisfy :: (Char -> Bool) -> Parser Char
satisfy f = parser $ \s -> case s of
    [] -> []
    a:as -> [(a,as) | f a]

char :: Char -> Parser Char
char = satisfy . (==)

alpha,digit :: Parser Char
alpha = satisfy isAlpha
digit = satisfy isDigit

string :: String -> Parser String
string = mapM char

infixr 5 +++
(+++) :: Parser a -> Parser a -> Parser a
(+++) = mplus

many, many1 :: Parser a -> Parser [a]
many p = return [] +++ many1 p
many1 p = liftM2 (:) p (many p)

Today he gave us an assignment to introduce "a left-biased, or short-circuiting version of (+++)", called (<++). His hint was for us to consider the original implementation of (+++). When he first introduced +++ to us, this was the code he wrote, which I am going to call the original implementation:

infixr 5 +++
(+++) :: Parser a -> Parser a -> Parser a
p +++ q = Parser $ \s -> runParser p s ++ runParser q s

I have been having tons of trouble since we were introduced to parsing and so it continues.

I have tried/am considering two approaches.

1) Use the "original" implementation, as in p +++ q = Parser $ \s -> runParser p s ++ runParser q s

2) Use the final implementation, as in (+++) = mplus

Here are my questions:

1) The module will not compile if I use the original implementation. The error: Not in scope: data constructor 'Parser'. It compiles fine using (+++) = mplus. What is wrong with using the original implementation that is avoided by using the final implementation?

2) How do I check if the first Parser returns anything? Is something like (not (isNothing (Parser $ \s -> runParser p s) on the right track? It seems like it should be easy but I have no idea.

3) Once I figure out how to check if the first Parser returns anything, if I am to base my code on the final implementation, would it be as easy as this?:

-- if p returns something then
p <++ q = mplus (Parser $ \s -> runParser p s) mzero
-- else
(<++) = mplus

Best, Jeff