Haskell: Left-biased/short-circuiting function
- by user2967411
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
