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 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
Finally applying ourselves
Applicative functors are a generalization of
Functors 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
as we can map a function
a -> b over it and get out a new
f which contains
bs 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
Chars, so they will be returning values that are either
Strings. But we’re going to want our to build up more elaborate values, which will require getting
Ints 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
int :: Parser Int int = read <$> some oneDigit where oneDigit = psym isDigit
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
(<$>) is just the infix form of
fmap. Here we use it to lift a
Parser String to
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
Maybes 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
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.
Applicatives support two more combinators that allow us to do just that:
(<*). 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
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
Applicatives, but one’s that support choice. This lets us choose between two parsers. If one fails, we try the second.
Sums 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
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
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!