Functor for a parser

As part of a homework assignment we are working on a parser in Haskell. We have this data type

newtype Parser a = Parser { parse :: String -> Maybe (a,String) }

This is clear to me,our parser gets a string are return expression from type a and the remaining unparsed string.

But next we are having this functor definition :

  instance Functor Parser where
       fmap f p = Parser $ \s -> (\(a,c) -> (f a, c)) <$> parse p s

And I'm completely lost. It seems to me that parse p s gives the parsed expression from type a but I can't understand what this fmap is actually doing and why it makes sense.

Hope that someone can give me a clue.

Thanks!

Solution

Given a parser p, fmap fn p will create a new parser which parses the same text as p but then applies fn to the output. For instance, if you have a parser parseOptionalNumber :: Parser (Maybe Int), you can turn it into parseNumber :: Parser Int by doing parseNumber = fmap fromJust parseOptionalNumber (although you wouldn’t want to do this, as fromJust is partial).

As for the implementation, it works like this:

The whole thing is wrapped in Parser $ \s -> …, which creates a new parser which executes … given an input string s.
parse p s uses the function parse :: Parser a -> (String -> Maybe (a,String)) (from the definition of Parser a) to run the input parser p on the input string s, producing an output of type Maybe (a,String).
(<$>) is a synonym of the function fmap, but as an operator rather than a function. It maps the function on the left over the Maybe (a,String) output on the right. The function it maps is \(a,c) -> (f a, c), which runs the given function f over the output (a,c) from the given parser p.

Hopefully that makes sense; if it didn’t, you may find it more useful to rewrite fmap in a less compact form:

instance Functor Parser where
    fmap f inParser = Parser $ \inputStr ->
        case (parse inParser inputStr) of
            Nothing -> Nothing
            Just (result, leftoverString) -> Just (f result, leftoverString)