In 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
Parser an applicative functor, we have two functions that must be defined,
<*>. 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
<*> 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
<* functions are used to state what value should be returned when using the operator. In other words,
a *> b performs
b, and returns the value found in
b. The computation
a <* b performs
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.