# Fun with Applicative Functors, Pt I

This post will the the first entry in a series about using Applicative Functors in Haskell projects. Applicatives are a nice abstraction for dealing with effectful computations in Haskell, similar to monads. They are somewhat more restricted than monads in their expressive power, but because of this you can find them hiding just about everywhere.

Since this is our first Haskell post, we’ll start out pretty slowly, but hopefully ramp up the speed in subsequent posts. That said, the following assumes at least a passing knowlege of the language. Hopefully what’s going on will be clear and whet your appetite if not. In any case there are several great places to get started.

In this series, we’ll take a look at using applicatives for a few different use cases. This time we’ll use them for parsing simple expressions; later, we’ll try them for doing some actions in the IO monad and for handling command-line arguments.

In the end, our goal will be to write a small program that can roll some dice for us.

## Let’s get Rolling

Rolling just one type of die would be pretty boring, so let’s create a program that rolls a collection of dice of varying dimensions. If you’ve ever played classic pen-and-paper RPGs (if so you should check out our mobile app RPG Buddy) you’ll recognize these polyhedral dice and the notation for specifying them: A “dX” is a die with X sides. Rolling a “dX” can produce any of the values from 1 to X.

Multiple dice of the same size may be rolled at once, and this is written as “NdS”: i.e., roll N S-sided dice and sum the result. Different size dice can be rolled simultaneously and we can also add a constant value.

As a complete example, `"3d6+1d4+2"`

denotes rolling 3 six-sided dice, 1 four-side die, summing all the face values and adding 2. We’ll call strings like these “dice expressions”.

Given these expressions, let’s make a program called roller. It’s goal in life is to simulate rolling a collection of polyhedral dice denoted by an expression passed in as a command-line argument. It s usage might look something like this:

```
$ roller 3d10 + 2
23
$ roller 1d4
3
$ roller 5
5
```

Great. Now, how do we want to represent these expressions as data in Haskell? Since we can have any number of terms in the expression, we’re going to be looking for some kind of recursive type. Let’s try

```
data DiceExp =
Die Int Int
| Const Int
| Sum DiceExp DiceExp
```

So, our expression can be one of three things. Either a x-sided die n times, a constant integer, or the sum of two other dice expressions. We can create one of these using a combination of these three constructors, so `"3d6+2"`

would be:

`Sum (Die 3 6) (Const 2)`

Very nice! But typing out expressions like this will quickly become cumbersome. Rather we’d prefer to parse these expressions directly from strings. Since we’re going to need to do this anyway for our CLI interface, let’s work on that next.

## Parsing dice expressions

So we’d now like to write a function `parse :: String -> Maybe DiceExp`

, that is, a function which takes a string and returns a dice expression if possible, but instead gives us nothing if the expression is invalid. In other languages we might use something like regular expressions to get back the matching parts of the string we need to build up our data structure. We’ll do something similar for our Haskell program, but using the regex-applicative package from hackage.

This library gives us parsers with types `RE s a`

which mean that they match strings made up of symbols of type `s`

and return values of some type `a`

. The `a`

here will be polymorphic depending on what part of the expression we’re trying to extract, but since we’re planning on using strings for this tutorial, `s`

will always be `Char`

. We can abstract this detail away with a type alias:

`type Parser a = RE Char a`

Now we’re ready to start making parsers, but first let’s talk about `Applicative`

s.

## Finally applying ourselves

`Applicative`

functors are a generalization of `Functor`

s in Haskell, which are things that can be mapped over. A `Functor`

is a type that supports a mapping operation: `fmap :: Functor f => (a -> b) -> f a -> f b`

. This means that if we have an `f`

which contains `a`

s we can map a function `a -> b`

over it and get out a new `f`

which contains `b`

s instead. A concrete example of a `Functor`

are simple lists, where `fmap = map`

:

`fmap length ["foo", "bar", "quux"] = [3,3,4]`

This mapping ability will come in handy for our parsers. Natively they are going to be recognizing one or more `Char`

s, so they will be returning values that are either `Char`

s or `String`

s. But we’re going to want our to build up more elaborate values, which will require getting `Int`

s and values of our `DiceExp`

type. Since `Parser`

is a functor however, we can use `fmap`

to convert them into new parsers which give us the values we want.

Let’s take a bottom up approach. We’re going to need to recognize integers to create our dice expressions, so let’s start there.

`int`

will be a parser which, given a string like `"123"`

, returns the integer value `123`

.

```
int :: Parser Int
int = read <$> some oneDigit
where oneDigit = psym isDigit
```

The `psym`

function returns a parser that recognizes any digit that satisfies the passed in predicate function. We’ll use that to recognize integer digits using `isDigit :: Char -> Bool`

from the `Data.Char`

package. Then using the `some`

combinator, we can recognize one or more of them. `some oneDigit`

will recognize the strings we need, but it returns a `String`

. This is where we use the fact that a `Parser`

is a `Functor`

. `(<$>)`

is just the infix form of `fmap`

. Here we use it to lift a `Parser String`

to `Parser Int`

.

Now comes the point where we’ll use the souped up `Applicative`

interface. Whereas `Functor`

lets us map a function of one argument `a -> b`

, `Applicative`

allows us the ability to lift functions of any arity.

As a small example, consider the `Maybe`

type, which is also an `Applicative`

instance. We can lift addition to work on `Maybe`

s like so:

```
addMaybes :: Maybe Int -> Maybe Int -> Maybe Int
addMaybes x y = (+) <$> x <*> y
```

So we’ve taken addition, which works on regular numbers, and made it work for `Maybe`

s.

Each `Applicative`

type will work a little differently when mapped over like this. `Maybe`

represents computations that can fail, so if either of the arguments fail (are `Nothing`

) the entire thing fails.

```
addMaybes (Just 3) Nothing = Nothing
addMaybes (Just 3) (Just 2) = Just 5
```

## Throwing out the trash

To continue on our parsing problem, we need to have parsers that recognize parts of the input that we don’t want to keep around. `Applicative`

s support two more combinators that allow us to do just that: `(*>)`

and `(<*)`

. These guys will sequence two parsers together, but they will only return the result on the side the operator is pointing to.

Now we’re equipped to recognize the syntax for rolling x n-sided die:

```
die :: Parser DiceExp
die = Die <$> int <* sym 'd' <*> int
```

As we can see in the type signature, we are recognizing one of our dice expressions. First we grab and integer, and then we recognize the literal character `'d'`

. Throwing that away, we take another integer. Then we pass both of the integers from the `int`

parser back to our constructor `Die`

and we’re left with our expression.

Constants are even more straight forward, requiring only `Functor`

:

```
const :: Parser DiceExp
const = Const <$> int
```

For our last parser, we’ll need to use another combinator. `(<|>)`

, which is part of the `Alternative`

type class—related to `Applicative`

s, but one’s that support choice. This lets us choose between two parsers. If one fails, we try the second.

To get `Sum`

s is a little tricky, but basically after getting a beginning `term`

—any expression that’s not itself a `sum`

—we collect a list of additional terms. Once we build up this list of terms, we can use a fold to build up into a `Sum`

of `Sum`

s recursively.

Here’s the function definition:

```
diceExp :: Parser DiceExp
diceExp = foldl1 Sum <$> terms
where terms = (:) <$> term <*> many (sym '+' *> term)
term = die <|> const
```

## Testing it out

Equipped with our `diceExp`

parser, let’s play around a bit and see how our work is progressing. regex-applicative gives us a matching operator `(=~) :: String -> Parser a -> Maybe a`

. So using our parser we can try matching some strings:

```
ghci> "1" =~ diceExp
Just (Const 1)
ghci> "3d6" =~ diceExp
Just (Die 3 6)
ghci> "3d6+2" =~ diceExp
Just (Sum (Die 3 6) (Const 2))
ghci> "1dmillion-a few"
nothing
```

## Finishing up

Now that we have a parser which can recognize expressions, we will just bundle it into our `parse`

function. This preprocesses the input to remove whitespace and then returns our expression.

```
parse :: String -> Maybe DiceExp
parse s = let s' = filter (not . isSpace) s in s' =~ diceExp
```

We can use this now to implement our command-line application. But that’s for next time!

You can find the working code for the program on Github. Look at `Parse.hs`

and `Types.hs`

—No peeking at the other files unless you want spoilers for the next parts. See you then!

## No comments:

## Post a Comment