Wednesday, August 7, 2013

Fun with Applicative Functors, Pt I

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
$ roller 1d4
$ roller 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 Applicatives.

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 Chars or 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 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 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 Maybes.

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. Applicatives 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 Applicatives, but one’s that support choice. This lets us choose between two parsers. If one fails, we try the second.

To get 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 Sum of Sums 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"

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