CODEWITHSUNDEEP
parsinghaskellparser-combinators
Yusuf
Yusuf

Reputation: 491

Haskell Parser Combinators - String function

I have been reading a tutorial about parser combinators and I came across a function which I would like a bit of help in trying to understand.

satisfy :: (Char -> Bool) -> Parser Char
satisfy p = item `bind` \c ->
  if p c
  then unit c
  else (Parser (\cs -> []))

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

natural :: Parser Integer
natural = read <$> some (satisfy isDigit)

string :: String -> Parser String
string [] = return []
string (c:cs) = do { char c; string cs; return (c:cs)}

My question is how does the string function work or rather how does it terminate, say i did something like:

let while_parser = string "while"

and then i used it to parse a string say for example parse while_parser "while if" , it will correctly parse me the "while".

however if i try something like parse while_parser "test it will return [].

My question is how does it fail? what happens when char c returns an empty list?

Upvotes: 0

Views: 956

Answers (1)

user2297560
user2297560

Reputation: 2983

Let's say your Parser is defined like this:

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

Then your Monad instance would be defined something like this:

instance Monad Parser where
  return x = Parser $ \input -> [(x, input)]
  p >>= f = Parser $ \input -> concatMap (\(x,s) -> runParser (f x) s) (runParser p input)

You're wondering what happens when char c fails in this line of code:

string (c:cs) = do { char c; string cs; return (c:cs) }

First, let's desugar it:

string (c:cs) = char c >>= \_ -> string cs >>= \_ -> return (c:cs)

Now the part of interest is char c >>= \_ -> string cs. From the definition of char and subsequently the definition of satisfy we see that ultimately runParser (char c) input will evaluate to [] when char c fails. Look at the definition of >>= when p is char c. concatMap won't have any work to do because the list will be empty! Thus any calls to >>= from then on will just encounter an empty list and pass it along.

One of the wonderful things about referential transparency is that you can write down your expression and evaluate it by substituting definitions and doing the function applications by hand.

Upvotes: 1

Related Questions