## Create an Applicative Parser

Posted on May 7, 2013In this post, we take our previously made monadic parser library, and also make it an instance of the applicative functor class. Since a monad happens to be an applicative functor, there are not really any increases in functionality that will be made. Instead, making the parser an applicative functor will allow us to use functions that are provided for applicative functors to write our parser in a different style for many use cases. Doing this will allow us to write a parser in a different, and sometimes more clean way.

## Making a Functor of the Data Type

In order to make `Parser`

a functor, we must create one function, `fmap`

. The function `fmap`

has the type `Functor f => ( a -> b ) -> f a -> f b`

. This type implies a couple things about `fmap`

. The first is that it takes in a function that makes one datatype to another. The second is that it also takes a functor that carrys the first type in it, and outputs a functor with the second data type in it. So lets try and define `Parser`

as a functor by taking advantage of the fact that `Parser`

is a monad as well.

```
instance Functor Parser where
fmap :: Functor f => (a -> b) -> f a -> f b
fmap f ma = do
a <- ma
return (f a)
```

That’s it! Mind you, since it is known that a monad is also a functor, there is a function that is the equivalent of `fmap`

. This function is called `liftM`

. So we could rewrite our previous code to be like this.

```
import Control.Monad
instance Functor Parser where
fmap = liftM
```

## Verifying that the type is a Functor

Normally, if we were defining a functor from scratch, we would have to show that the type satisfies the following laws.

```
-- That there is an identity function, a function that maps anything to itself.
fmap id == id
-- Distributive property. Given a function composed of f and g, the result of fmapping them composed is the
-- result of them being fmapped separately.
fmap (f . g) == fmap f . fmap g
```

Fortunately for us, the `Parser`

type has already been shown to be a monad. Since the monad is a specialization of the functor type, we can infer that it also satisfies these laws on top of the the monad laws we proved earlier!

## Making an Applicative Functor of the Data Type

To make `Parser`

an applicative functor, we have two functions that must be defined, `pure`

and `<*>`

. The function `pure`

has a type of `Applicative f => a -> f a`

. That is, it puts normal data types into an applicative functor. The function `<*>`

has a type of `Applicative f => f (a -> b) -> f a -> f b`

. In other words, `<*>`

is a function that applies values to functions in an applicative functor context. So let’s try and define `Parser`

as an applicative functor, keeping in mind that `Parser`

is a monad.

```
import Control.Applicative hiding (many)
instance Applicative Parser where
pure a = return a
(<*>) ff fa = do
f <- ff
a <- fa
return (f a)
```

Looking at the `return`

function that a monad has, you can see it has a very similar type structure `Monad m => a -> m a`

. Since `Parser`

is a monad, we can just drop `return`

in as the function to use when we use `pure`

. The `<*>`

function is a little more complicated. We had to unroll the function and the value to combine it into the result. However, like most things in haskell, there is a function that is the monad equivalent to `<*>`

. The monad equivalent for `<*>`

is called called `ap`

. The function `ap`

has a very similar type structure `Monad m => m (a -> b) -> m a -> m b`

, so we can just drop it in as the function to use when calling `<*>`

. So let’s rewrite our instance definition:

```
import Control.Applicative hiding (many)
import Control.Monad
instance Applicative Parser where
pure = return
(<*>) = ap
```

## Verifying that the type is an Applicative Functor

If we were defining `Parser`

as an applicative functor from scratch, there would be a few laws we would have to make sure it follows.

```
-- There is an identity, a function that maps anything to itself. In this case it's `pure id`
pure id <*> u == u
-- We can compose values together in an expected way.
pure (.) <*> u <*> v <*> w == u <*> (v <*> w)
-- Putting values into the context of an applicative functor doesn't change the operations that are done to those
-- values.
pure f <*> pure x == pure (f x)
-- Similar to previous one, the order we apply values and functions should not change the value in the applicative functor.
u <*> pure x == pure (\f -> f x) <*> u
```

Yet again, we are fortunate enough to have made `Parser`

a monad first, as a monad must follow these laws in order for it to be a monad. Since we know `Parser`

is a monad, we do not have to check these by hand.

## Utility of Being an Applicative Functor

So what useful things do we get by making `Parser`

an applicative functor? Well, as described at the beginning, making `Parser`

an applicative functor gives us a little bit more stylistic freedom in how we make our parser. To show this, we will recreate the simple calculator parser we made in the first parser post. Previously, our parser looked like this:

```
digit = oneof "0123456789"
integer = many1 digit
spaces = many $ char ' '
expression = expression' `mappend` integer
expression' = do
char '('
spaces
operator
spaces
expression
spaces
expression
char ')'
return ""
```

Let’s modify it slightly so that we do return something in the expression. This will make the applicative functor style more prominent, as well as make the calculator useful. To start off, we will show this done monadically.

```
data Expression = Expr Op Expression Expression | Number Int deriving Show
data Op = Add | Sub | Div | Mul deriving Show
-- keep these functions the same as they were before
spaces = many $ char ' '
digit = oneof "0123456789"
expression = expression' `mplus` integer
-- change these ones to return something useful after parsing.
operator = liftM toOp $ oneof "+*/-"
toOp '+' = Add
toOp '-' = Sub
toOp '/' = Div
toOp '*' = Mul
integer = do
ds <- many1 digit
return $ Number (read ds ::Int)
expression' = do
char '('
spaces
op <- operator
spaces
ex1 <- expression
spaces
ex2 <- expression
char ')'
return $ Expr op ex1 ex2
```

Now compare this to the applicative functor way.

```
import Control.Applicative
data Expression = Expr Op Expression Expression | Number Int deriving Show
data Op = Add | Sub | Div | Mul deriving Show
-- keep these functions the same as they were before
spaces = many $ char ' '
digit = oneof "0123456789"
expression = expression' `mplus` integer
-- change these ones to return something useful after parsing.
operator = oneof "+*/-" >>= toOp
toOp '+' = Add
toOp '-' = Sub
toOp '/' = Div
toOp '*' = Mul
integer = Number . read <$> many1 digit
expression' = Expr <$> (char '(' *> op <* spaces)
<*> (expression <* spaces)
<*> expression
```

It’s a little different right? It’s as if we’re doing normal composition, but with some extra parsing on the inside. The best explanation I’ve heard of what is equivalent to an applicative functor I found on stackoverflow. That is, think of an applicative functor as a way to zip values together to be used on a function. In our case, we are zipping our parser bits together to be used to make a data type. The `*>`

and `<*`

functions are used to state what value should be returned when using the operator. In other words, `a *> b`

performs `a`

then `b`

, and returns the value found in `b`

. The computation `a <* b`

performs `a`

then `b`

, and returns the value found in `a`

. Using those we can direct what parts of the parsed value we want to keep, to be used to make our `Expression`

data type. As I said before, it’s not necessary to have this style, but for at least me it reads better. Just like before, you can find the code for these posts here.