# 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.