How can I instance `Functor` for a type with two parameters?

Question

Background. In one of my classes we've been exploring the Parser monad. The Parser monad is typically defined as either

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

Or as

newtype Parser a = Parser (String -> Maybe (a, String))

In either case, we can instance Parser as a Functor using code that works in both cases:

instance Functor Parser where
  fmap f (Parser p) = Parser (fmap applyF . p)
    where applyF (result, s) = (f result, s)

If we have a Parser built to return Maybe (a, String), this applies f to the result if the result exists. And if we have a Parser built to return [(a, String)], this applies f to each of the results returned in the list.

We can instance Applicative, Monad, MonadPlus, and Alternative is similarly generic ways (so that they work either for Maybe or []).

Question. If I parameterize Parser based on the type used to wrap the result, how can I instance it for Functor and friends?

newtype Parser m a = Parser (String -> m (a, String))

-- How do I instance `Parser` as a Functor if `m` is a Functor?

Answer 1

You can here construct a constraint that m should be a type that is an instance of Functor as well, and then fmap on that result:

instance Functor m => Functor (Parser m) where
    fmap f (Parser p) = Parser (\x -> fmap g (p x))
        where g (r, s) = (f r, s)

Here g is thus a function that performs the mapping f on the first element of the tuple. We thus use that g as a "mapping" function over the result.

This will thus work for any m that is an instance of Functor, like a Maybe, a [], a Tree, etc.