From Get Programming with Haskell by Will Kurt This article takes a deep look at the Applicative Type Class using the example of the List class.

---

Save 37% on Get Programming with Haskell. Just enter code fcckurt into the discount code box at checkout at manning.com.

---

List as a Context

The List type, being a fundamental example of nearly everything in Haskell, is both a container and a context. List as a container is easy to understand. A list is a chain of buckets of whatever type of data you want to hold. List is a member of Applicative and there has to be a way to view list as a context.

The reason context matters for a list is because using Applicative requires that we answer the question “What does it mean to apply a function to two or values, in the context of a list?” For example, what does [1000,2000,3000] + [500,20000] mean? The naive assumption might be that

[1000,2000,3000] + [500,20000] = [1000,2000,3000,500,20000]

But this is “adding two lists,” which is concatenation (the ++ operator for lists). What we’re curious about is knowing what it means to combine two values in the context of list using addition. In terms of applicative we’d read this statement as:

 
 pure (+) <*> [1000,2000,3000] <*> [500,20000]
 

The list data structure doesn’t give us enough information to say what this means. To understand how we add two values in a list we need some extra context to interrupt the general idea of applying a binary function to values in lists.

The best way to understand list as a context is that it describes non-deterministic computation. Normally we think of programming as purely deterministic. Each step in the computation is followed by another in a precise order that yields one, final result. In non-deterministic computing, we’re computing multiple possibilities at once. In terms of thinking non-deterministically, when we add values in the context of a list we’re adding together all possible values from the two contexts. We can see the somewhat surprising result of using <*> with Lists in GHCi:

 
 GHCi> pure (+) <*> [1000,2000,3000] <*> [500,20000]
 [1500,21000,2500,22000,3500,23000]
 

Adding together two Ints in the context of a List means adding all possible combinations of the values in those lists.

Container vs context

It’s important to take a moment and point out the major differences between a list as a container and a list as a context:

• A list as a container is a sequence of values that holds any type. Each item in the list points to the next one or to the empty list.
• A list as a context represents a set of possibilities. Think of a list as a context as being a single variable that can contains many possible values.

Don’t be fooled by your familiarity with list as a container. Both Maybe and IO are much simpler contexts to reason about. A Maybe Int is a single Int value in the context that it may be missing. An IO Int is an Int value in the context that it was produced by some IO action that may have produced side-effects or other issues. A [Int] is an Int in the context that there are potentially many possible values for that Int. Because there are many possible values that [Int] could have, when we apply a function (Int -> Int -> Int) in the context of a list we must think non-deterministically and compute all possible results of that operation.

A game show example

As an example, suppose you’re on a game show and you get to choose one of three doors and one of two boxes. Behind the doors are prizes worth $1000, $2000 and $3000. We don’t know which we’ll get, but we can represent this as a list:

 
 doorPrize :: [Int]
 doorPrize = [1000,2000,3000]
 

After the door you choose one of two boxes, a box can contain either $500 or $20,000. We can represent these possibilities as list as well:

 boxPrize :: [Int]
 boxPrize = [500,20000]

In a deterministic context, you can only open one door, and only pick one box, getting only one prize. If we non-deterministically think about this problem we’re computing all possible combinations of doors we can open and boxes we can pick. Deterministically if we want to talk about prize, we’re talking about the one prize we can win. Here’s a visualization of the deterministic and non-deterministic ways to understand our prize:

---

Figure 1 Lists as non-deterministic computing are hard because we normally think deterministically.

---

The equation for our totalPrize in a deterministic world would be the following (we’re using the prefix (+) to easily compare it with the Applicative version):

 
 totalPrize :: Int
 totalPrize = (+) doorPrize boxPrize
 

In a non-deterministic context, we’re talking about all possible prizes that can be won. We can describe the non-deterministic totalPrize with this function:

---

Figure 2 non-deterministic computing computes on all possible paths, rather than one.

---

In GHCi we can see that totalPrize represents all possible prizes that can be won.

 
 GHCi> totalPrize
 [1500,21000,2500,22000,3500,23000]
 

When we add two lists in context we get the combination of all possible worlds. For each door prize, we can pick one the two possible box prizes. The results of adding two lists within the context of a list are all possible solutions in our non-deterministic world.

Next, we’ll look at two more examples of practical non-deterministic computing. We’ll use non-deterministic computing to compute all non-prime numbers allowing us to easily identify primes. Then we’ll used non-deterministic computing to quickly generate a set of possible test data.

Quick check

Solve this problem: if the boxes contained a prize multiplier instead of an additional prize. The Multipliers are 10x and 50x

Generating the First N prime numbers

A prime number is any number divisible by only one and itself. Suppose we wanted to generate a list of prime numbers. An amazingly simple method for computing a list of primes exists using the Applicative properties of a list. Here’s the basic process.

• Start with your list from 2 to n

• Determine all the non-prime numbers (i.e. composite numbers)

• Filter our all items from the list that aren’t composite

The only question remaining is “how do we compute the composite numbers?” A composite number is any number that can be made by multiplying two or more other numbers together. We can easily build this list by multiplying each number in our [2 .. n] list by itself. How can we do this easily? With Applicative! For example if we have [2..4] we can use multiplication *, pure and <*> to build our list of all possible numbers made from these numbers:

 
 GHCi> pure (*) <*> [2 .. 4] <*> [2 .. 4]
 [4,6,8,6,9,12,8,12,16]
 

This list is inefficient as it includes numbers out of our range as well as duplicate numbers. It’ll include every composite number in our range. Given this bit of code we can easily write our function for listing all prime number to n:

 
 primesToN :: Integer -> [Integer]
 primesToN n = filter isNotComposite twoThroughN
  where twoThroughN = [2 .. n]
        composite = pure (*) <*> twoThroughN <*> twoThroughN
        isNotComposite = (not . (`elem` composite))
 

Though not the most efficient prime number generating algorithm, this is incredibly easy to implement and works well enough for reasonably small ranges:

 
 GHCi> primesToN 32
 [2,3,5,7,11,13,17,19,23,29,31]
 

If you ever need to whip up a quick prime number generator, this little trick can be a useful tool to have.

Quickly generating large amounts of test data

A User can be created in different contexts using applicative. We used this user type for a user in a video game:

 
 data User = User {
      name :: String
    , gamerId :: Int
    , score :: Int
    } deriving Show
 

We already know that we can use Applicative to create instances of User in the context of both IO and Maybe. To demonstrate how powerful the list context is, we’ll do the same thing, only to create a large amount of test data.

Suppose we have a list of user names, some typical and others problematic in some cases. Thinking of lists as context testNames represents “possible names”:

 
 testNames :: [String]
 testNames = ["John Smith"
             ,"Robert'); DROP TABLE Students;--"
             ,"Christina NULL"
             ,"Randall Munroe"]
 

We want to test some “possible gamer ids” with gamerIds:

 
 testIds :: [Int]
 testIds = [1337
           ,0123
           ,999999]
 

And we want to make sure we have some possibly troublesome scores as well:

 
 testScores :: [Int]
 testScores = [0
             ,100000
             ,-99999]
 

What we want is to generate some test data that includes all possible combinations of these values. This means non-deterministically computing a list of possible users. We could do that by hand but that’d mean writing out 4 x 3 x 3 = 36 entries! Plus, if we later decide to add another value to any of those lists it means a lot of work for us.

Instead we can use the Applicative properties of list to non-deterministically generate our test data for us! This is how we’ll do it:

 
 testData :: [User]
 testData = (pure User) <*> testNames
                        <*> testIds
                        <*> testScores
 

In GHCi we can see that we’ve successfully created a list of all 36 possible combinations of these values. Even better to update our list we only have to add whatever values we like to testNames, testIds or testScores:

 
 GHCi> length testData
 36
 GHCi> take 3 testData
 [User {name = "John Smith", gamerId = 1337, score = 0}
 ,User {name = "John Smith", gamerId = 1337, score = 100000}
 ,User {name = "John Smith", gamerId = 1337, score = -99999}]
 

Using the List type to perform non-deterministic computing shows how powerful the Applicative types class can be when working with contexts!

Quick check

Add your own name to the testNames and regenerate the data. How many examples are there now?

Summary

In this article, the objective was to give you a deeper insight into the Applicative type class. We formally introduced you to the full Applicative type class, which includes the <*> operator and the pure method. The role of pure is to take normal values and put them into the context we need, for example turning an Int into a Maybe Int. We also focused on exploring the different between “containers” and “contexts” by explore a list as a context. Contexts differ from the containers in that they require us to understand something about the computation happening beyond what the data structure alone tells us. For lists, this means representing non-deterministic computation, rather than a container for sequential data. Let’s see if you got this…

Quiz Question #1: To prove that Applicative is strictly more powerful than Functor, write a universal version of fmap, called allFmap, that defines fmap for all members of the Applicative type class. Because it works for all instances of Applicative, the only functions you can use are the methods required by the Applicative type class. To get you started here’s your type signature:

allFmap :: Applicative f => (a -> b) -> f a -> f b

When you’re done, test this out on List and Maybe which are both members of Applicative:

GHCi> allFmap (+ 1) [1,2,3]

[2,3,4]

GHCi> allFmap (+ 1) (Just 5)

Just 6

GHCi> allFmap (+ 1) Nothing

Nothing

Quiz Question #2: Take the following example and use non-deterministic computing with Lists to determine how much beer you need to purchase to assure there’ll be enough:

• You bought beer last night but you don’t remember whether it was a 6-pack or a 12 pack

• You and your roommate each had two beers last night.

• You’re having either two or three friends over tonight, depending on who can come.

• For a long night of gaming you expect the average person to drink three to four beers.

Hopefully, you found this article informative and interesting.

---

For more on Haskell, check out the book on liveBook here and see this Slideshare presentation.

---