CODEWITHSUNDEEP
haskellmonads
user4959635
user4959635

Reputation:

Haskell: What is a parser in a monadic parser?

I'm reading this paper regarding a monadic parser in Haskell and as a newbie I cannot understand the following construct:

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

instance Monad Parser where
  return a = Parser (\cs -> [(a,cs)])
  p >>= f  = Parser (\cs -> concat [parse (f a) cs’ |
                               (a,cs’) <- parse p cs])

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

It says in the text that:

Using a deconstructor function for parsers defined by parse (Parser p) = p, the parser p >>= f first applies the parser p to the argument string cs to give a list of results of the form (a,cs’), where a is a value and cs’ is a string. For each such pair, f a is a parser which is applied to the string cs’.

Why is (f a) and not f a parser? And why is passing the 'a' necessary?

Upvotes: 0

Views: 307

Answers (1)

icktoofay
icktoofay

Reputation: 129119

The type of (>>=), instantiated with the monad Parser, has this type signature:

(>>=) :: Parser a -> (a -> Parser b) -> Parser b

Hence, when defining p >>= f, p has type Parser a and f has type a -> Parser b. That’s why f a is a parser and not f: f is a function from a to Parser bs.

The reason it’s that way is that without it, we could combine parsers… but we would never be able to use the result of the previous parser in the next parse! By passing the result of the previous parser forward, we can build up data out of the results of multiple parsers, e.g.:

parseTwoOf :: Parser a -> Parser (a, a)
parseTwoOf p = p >>= \first -> p >>= \second -> return (first, second)

Upvotes: 2

Related Questions