Haskell Parser Combinators - String function

Question

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?

I suspect char c doesn't "return an empty list", rather it fails on end of input. The bind operator then propagates that failure. — MathematicalOrchid
– MathematicalOrchid, Commented Aug 16, 2016 at 13:20
@MathematicalOrchid From the definition of satisfy when char fails it will return a function which generates an empty list. What do you mean by propagate failure? — Yusuf
– Yusuf, Commented Aug 16, 2016 at 14:09

user2297560 · Accepted Answer · 2016-08-16 14:55:16Z

1

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.

answered Aug 16, 2016 at 14:55

user2297560

2,9931 gold badge16 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

chepner Over a year ago

Technically, it desugars to char c >> string cs >> return (c:cs), since the desugaring is independent of whatever monad is in use. m >> f is usually, but isn't required to be, implemented as m >>= \_ -> f.

user2297560 Over a year ago

@chepner Yep. I was too lazy to explain a tangential detail.

Yusuf Over a year ago

thank you, i think i kind of get it, but where does the recursive call to string fit in to all of this?

user2297560 Over a year ago

Note that in the definition of >>=, the call to f (which is \_ -> string cs in this example) is inside the function passed to concatMap. But since (runParser p input) is an empty list, that function is never actually used. Thus, the recursion doesn't happen.

Collectives™ on Stack Overflow

Haskell Parser Combinators - String function

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related