Epsilon

Create an Applicative Parser

Posted on May 7, 2013

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

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.

comments powered by Disqus