Lesson 29. Lists as context: a deeper look at the Applicative type class

After reading lesson 29, you’ll be able to

In the preceding lesson, you learned how to use the <*> (pronounced app) operator to extend the power of Functor’s <$> (pronounced fmap) operator. In this lesson, you’ll take a closer look at the Applicative type class. You’ll explore the difference between types that represent a container and types that represent a context. You’ll finish by looking at the powerful things you can achieve by using lists as a context.

Consider this

A breakfast place offers you the choice of the following:

What are all the possible meals you could choose, and how can you use List to help?

29.1. Introducing the Applicative type class

The Applicative type class allows you to use functions that are inside a context, such as Maybe or IO. As you saw in the preceding lesson, this extends the power of the Functor type class. Because of the way that Applicative works with Functor, Functor is a superclass of Applicative. See figure 29.1.

Figure 29.1. Functor is the superclass of applicative. Figure 29.2 provides the definition of Applicative with its two required methods.

One tricky thing in this definition is that there are two constraints on your type variable f. The first says that f is a Functor, which enforces that Applicative must be a Functor, and then you define f as your stand-in for Applicative. In your method signatures, f is a variable for any Applicative (see figure 29.2). Notice that the operator <*> has the same type signature as your fmap, except the function argument is also in a context. This small difference in <*> allows you to chain together larger sequences of functions inside members of the Functor type class. Here are a few examples of using <$> and <*> to perform mathematical operations on Maybe types: 

GHCi> (*) <$> Just 6 <*> Just 7
Just 42
GHCi> div <$> Just 6 <*> Just 7
Just 0
GHCi> mod <$> Just 6 <*> Just 7
Just 6

Figure 29.2. Type class definition for Applicative

This solution may seem either elegant or confusing, depending on how comfortable you are with Haskell’s infix binary operators. Undoubtedly, using <$> and <*> can initially seem confusing. Further complicating the issue is that unlike <$> and fmap, <*> has no equivalent function. If you’re struggling with these operators, the best solution is practice. Try going back to some of the examples in unit 1 and change values used as arguments to Maybe values. Remember, because of fmap and <*>, you don’t need to rewrite any functions to work with Maybe values.

Quick check 29.1

Q1:

Use <$> and <*> to combine two Maybe String types with ++.

QC 29.1 answer

1: 

GHCi>(++) <$> Just "Learn" <*> Just " Haskell"
Just "Learn Haskell"

 

29.1.1. The pure method

The function pure is the second method required by the Applicative type class. The pure method is a useful helper function for taking an ordinary value or function and putting it into a context. The best way to understand pure is to play around with it in GHCi. In the example of a Maybe, pure will return a Just: 

GHCi> pure 6 :: Maybe Int
Just 6

You can also use pure to put a function into the context of Applicative. For example, if you want to add 6 to (Just 5), you can use either fmap or pure: 

GHCi> (6+) <$> Just 5
Just 11
GHCi> pure (6+) <*> Just 5
Just 11

Though these examples are fairly simple, in practice you’ll frequently want a quick way to transform a value into the desired Applicative type. In our visual language, pure also performs an important role, as shown in figure 29.3.

Figure 29.3. The pure method means you always have a way to take an ordinary type and put it in a context.

Because of pure, you can take any value that’s not in a context and trivially put it in one. This is vital to allowing all possible computations in a context.

Quick check 29.2

Q1:

Make the String "Hello World" into an IO String.

QC 29.2 answer

1: 

hello :: IO String
hello = pure "Hello World"

 

29.2. Containers vs. contexts

So far, we’ve talked somewhat loosely about the difference between parameterized types that represent containers and contexts. At this point, you need to be a bit clearer about what you mean by these terms. The reason is that unlike Functor, Applicative and the next lesson’s type class Monad make sense only when you’re talking about types as a context. Here’s the distinction in a nutshell:

Let’s explore this further. The best test of whether a type is a container is whether you can tell what it does, independent of its name. For example, consider the 2-tuple (a,b). You could implement the same type named Blah.

Listing 29.1. A poorly named 2-tuple is still the same thing 
data Blah a b = Blah a b

Even with a completely useless name like Blah, it’s hard to argue that this type is any different than a regular tuple pair (a,b).

The Data.Map type is another, similar structure. You could call this a Dictionary, a Binary-SearchTree, a MagicLookupBox, and so forth. But what the type means is implied by the data structure itself. Even if the entire set of functions around Map were written in an alien language, you’d still quickly figure out what the type is used for. (Probably...eventually.)

It’s worth pointing out that the 2-tuple (,) and Data.Map are both instances of Functor but not instances of Applicative. Remember that the key power of Applicative is that it lets you apply a function in a parameterized type. Another good way to differentiate containers from contexts is to ask, “Does it make sense to have a <type> function?” Maybe (a -> b) is a function from a -> b that itself might not exist because it was made via partial application with a Nothing value. An IO (a -> b) function is any function that’s operating in the world of IO. What does a Data.Map function mean? Likewise, what does a 2-tuple function mean? If you can answer these questions, you have the starting ground for figuring out the Applicative instance for these types.

When a type is a context, on the other hand, extra information is implied about the type, beyond its structure. The most obvious case is the IO type. When you first introduce parameterized types, you introduce the idea of a Box type.

Listing 29.2. The trivial Box type doesn’t seem much different from IO
data Box a = Box a

Clearly, Box is a uselessly trivial type. But there’s no difference at the data constructor level between Box and IO. IO, from our perspective, is just a data constructor that wraps types that came from IO (there’s much more to the IO type, but not that you can immediately see).

The Maybe type is another context type. Suppose you want to create a parameterized type for a resource-constrained computation. You could imagine this type as follows.

Listing 29.3. A type representing if there are enough resources to continue 
data ResourceConstrained a = NoResources | Okay a

Behind the scenes, there would be a lot of magic determining resource usage, but this type is no different from Maybe at the type-constructor level. Most of the information about this type is in a context that you assume about the type itself.

The best way to understand this distinction between container and context is to look at an example. List turns out to be the perfect case. It’s easy to understand List as a container because it’s a common data structure. But List also describes a context. If you understand how List can be a container and a context, you’re on the path to truly understanding Applicatives.

Quick check 29.3

Q1:

Suppose you want to make it so that (pure +) <*> (1,2) <*> (3,4) = (1+2,1+4,2+3,2+4) = (3,5,5,6). Why doesn’t this work?

QC 29.3 answer

1:

This doesn’t work because (3,5,5,6) is an entirely different type than (1,2) or (3,4). The first is type (a,b,c,d), and the other two are (a,b).

 

29.3. 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. List is basically a chain of buckets of whatever type of data you want to hold. But List is a member of Applicative, so there must be a way to view List as a context.

The reason context matters for a list is that to use Applicative, you need to be able to answer the question, “What does it mean to apply a function to two or more values in the context of a list?” For example, what does [1000,2000,3000] + [500,20000] mean? The naive assumption might be as follows: 

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

But this would be just adding two lists, which is concatenation (the ++ operator for lists). What you’re curious about is what it means to combine two values in the context of List by using addition. In terms of Applicative, you’d read this statement as follows: 

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

The List data structure alone doesn’t give you enough information to say what this means. To understand how you add two values in a list, you need extra context to interpret 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 nondeterministic computation. Normally, you 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 nondeterministic computing, you’re computing multiple possibilities all at once. In terms of thinking nondeterministically, when you add values in the context of a list, you’re adding together all possible values from the two contexts. You 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.

29.3.1. Exploring container vs. context with a list

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:

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 an IO action that may have produced side effects or other issues. An [Int] is an Int in the context that there are many possible values for that Int. Because there are many possible values for that [Int], when you apply a function (Int -> Int -> Int) in the context of a list, you must think nondeterministically and compute all possible results of that operation.

29.3.2. A game show example

As an example, suppose you’re on a game show and you get to choose one of three doors and then one of two boxes. Behind the doors are prizes worth $1,000, $2,000, and $3,000. You don’t know which you’ll get, so you can represent this as a list.

Listing 29.4. Nondeterministic possibilities for door values 
doorPrize :: [Int]
doorPrize = [1000,2000,3000]

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

Listing 29.5. Nondeterministic possibilities for box prizes 
boxPrize :: [Int]
boxPrize = [500,20000]

In a deterministic context, you can open only one door, and pick only one box, getting only one prize. But if you nondeterministically think about this problem, you’re computing all possible combinations of doors you can open and boxes you can pick. Deterministically, if you want to talk about prizes, you’re talking about the one prize you can win. Figure 29.4 presents the deterministic and nondeterministic ways to understand your prize.

Figure 29.4. Thinking of lists as nondeterministic computing is hard because you normally think deterministically.

The equation for your totalPrize in a deterministic world would be the following (you use the prefix (+) so it’s easy to compare with the Applicative version).

Listing 29.6. Deterministic door prize can represent only a single path 
totalPrize :: Int
totalPrize = (+) doorPrize boxPrize

In a nondeterministic context, you’re talking about all possible prizes that can be won. You can describe the nondeterministic totalPrize with the function shown in figure 29.5.

Figure 29.5. Nondeterministic computing computes on all possible paths, rather than just one.

In GHCi, you can see that totalPrize represents all possible prizes that can be won: 

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

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

Next you’ll look at two more examples of practical nondeterministic computing. You’ll use nondeterministic computing to compute all nonprime numbers, allowing you to easily identify primes. Then you’ll use nondeterministic computing to quickly generate a set of possible test data.

Quick check 29.4

Q1:

Solve this problem if the boxes contain a prize multiplier instead of just an additional prize. The multipliers are 10× and 50×.

QC 29.4 answer

1: 

boxMultiplier = [10,50]
newOutcomes = pure (*) <*> doorPrize <*> boxMultiplier

GHCi> newOutcomes
[10000,50000,20000,100000,30000,150000]

 

29.3.3. Generating the first N prime numbers

A prime number is any number divisible by only 1 and itself. Suppose you want to generate a list of prime numbers. There’s an amazingly simple method for computing a list of primes using the Applicative properties of a list. Here’s the basic process:

  1. Start with your list from 2 to n.
  2. Determine all the nonprime numbers (composite numbers).
  3. Filter out all items from the list that aren’t composite.

The only question remaining then is, “How do you compute the composite numbers?” A composite number is any number that results from multiplying two or more other numbers together. You can easily build this list by multiplying each number in your [2 .. n] list by itself. How can you do this easily? With Applicative! For example, if you have [2..4], you can use multiplication *, pure, and <*> to build your list of all possible numbers that are 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 your range as well as duplicate numbers. But it’ll include every composite number in your range. Given this bit of code, you can easily write your function for listing all prime numbers to n.

Listing 29.7. primesToN, a simple but inefficient primer algorithm 
primesToN :: Integer -> [Integer]
primesToN n = filter isNotComposite twoThroughN
 where twoThroughN = [2 .. n]
       composite = pure (*) <*> twoThroughN <*> twoThroughN
       isNotComposite = not . (`elem` composite)

Although 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.

29.3.4. Quickly generating large amounts of test data

In the preceding lesson, we showed how a User could be created in different contexts by using Applicative. You used this User type for a user in a video game: 

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

You used Applicative to create instances of User in the context of both IO and Maybe. To demonstrate how powerful the list context is, you’ll do the same thing, only to create a large amount of test data.

Suppose you have a list of usernames, some typical and others problematic in certain cases. Thinking of lists as context, testNames represents possible names.

Listing 29.8. Some testNames for your data 
testNames :: [String]
testNames = ["John Smith"
            ,"Robert'); DROP TABLE Students;--"
            ,"Christina NULL"
            ,"Randall Munroe"]

You want to test possible gamer IDs with gamerIds.

Listing 29.9. testIds with different values 
testIds :: [Int]
testIds = [1337
          ,0123
          ,999999]

And you also want to make sure you have possible troublesome scores as well.

Listing 29.10. Sample testScores for testing 
testScores :: [Int]
testScores = [0
             ,100000
             ,-99999]

What you want to do is generate test data that includes all possible combinations of these values. This means nondeterministically computing a list of possible users. You could do that by hand, but that would mean writing out 4 × 3 × 3 = 36 entries! Plus, if you later decide to add another value to any of those lists, it means a lot of work for you.

Instead, you can use the Applicative properties of List to nondeterministically generate your test data for you. You’ll do this exactly the same way you created User types for IO and Maybe in the preceding lesson.

Listing 29.11. Same pattern used for IO and Maybe to generate many test users 
testData :: [User]
testData = pure User <*> testNames
                       <*> testIds
                       <*> testScores

In GHCi, you can see that you’ve successfully created a list of all 36 possible combinations of these values. Even better, to update your list, you have to add whatever values you 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 nondeterministic computing shows how powerful the Applicative type class can be when working with contexts!

Quick check 29.5

Q1:

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

QC 29.5 answer

1: 

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

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

There are now 45 examples.

 

Summary

In this lesson, our objective was to give you a deeper insight into the Applicative type class. You were formally introduced to the full Applicative type class, which includes the <*> operator you learned in the preceding lesson, as well as the pure method. The role of pure is to take normal values and put them into the context you need; for example, turning an Int into a Maybe Int. You also focused on the differences between containers and contexts by exploring a list as a context. Contexts differ from containers in that they require you to understand something about the computation happening beyond what the data structure alone tells you. For lists, this means representing nondeterministic computation, rather than just a container for sequential data. Let’s see if you got this.

Q29.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 finished, 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

Q29.2

Translate the following expression into one where the result is a Maybe Int. The catch is that you may not add (or remove) anything to the code except pure and <*>. You can’t use the Just constructor or any extra parentheses. 

example :: Int
example = (*) ((+) 2 4) 6

Here’s the type signature for your answer:

exampleMaybe :: Maybe Int

Q29.3

Take the following example and use nondeterministic computing with Lists to determine how much beer you need to purchase to assure there will be enough: