Don't worry, your Parser is a functor

If you’re delving into the world of applicative parsers, at the very start you’ll encounter the following abstract type (or something similar):

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

This type represents a function that takes an input string and maybe produces a pair containing the parsed token with the rest of the string.

Once you’ve grasped the concept of the Parser type, you can explore how to make it a functor. Defining the Functor instance for Parser is a straightforward task:

instance Functor Parser where
    fmap f (P p) = P (\s -> f' (p s))
       where
            f' (Just (x, y)) = Just (x, f y)
            f' Nothing       = Nothing

The harder part is proving this definition is respecting functor laws. Even if these proofs are also straightforward, they require a bunch of writing and case analysis.

A Shortcut

Fortunately, there’s a quicker way to prove functor laws for Parser. We can leverage the compositionality of functors. Notice that Parser is the composition of three abstract types, all of which are functors: (,) String, Maybe, and (->) String. This compositionality extends to the fmap level, allowing us to express the Functor Parser instance more concisely:

instance Functor Parser where
    fmap f (P p) = P $ fmap (fmap (fmap f)) p

The only thing left is to prove that the composition of functors is a functor. But that is straightforward:

Lemma: for any two functions $f$ and $g$ such that $g\circ f$ is defined, and any two functors $L$ and $H$ such that $H \circ L$ is defined, it holds that $H\circ L$ is also a functor because $$H \left(L \operatorname{id}\right) = H \operatorname{id}= \operatorname{id},$$ $$H \left(L \left(g\circ f\right)\right) = H \left(L g\circ L f\right) = H \left(L g\right)\circ H\left(L f\right).$$

By applying this lemma, we can conclude that Parser is indeed a functor.

Challenges with Applicative

Now, when it comes to making Parser an Applicative instance, the journey becomes more intricate. The Applicative class introduces the pure and <*> methods, which are not as straightforward to adapt as fmap. For instance, defining pure for Parser requires the input string to be present in the resulting pair (pure x = P $ \s -> Just (s, x)), unlike pure for (,) String which is defined as pure x = ("", x).

Still, even with these difficulties, you can try to put as much as you can pure and <*> methods inside new definitions. You will notice that this can shorten you proofs.