Lesson 32. The list monad and list comprehensions
After reading lesson 32, you’ll be able to
- Use do-notation to generate lists
- Filter results in do-notation by using guard
- Further simplify do-notation with list comprehensions
At the end of the preceding lesson, you saw that List is an instance of Monad. You saw only a simple example of using List as a Monad to process a list of candidates.
Listing 32.1. The assessCandidateList function from the previous lesson
assessCandidateList :: [Candidate] -> [String]
assessCandidateList candidates = do
candidate <- candidates 1
let passed = viable candidate 2
let statement = if passed 3
then "passed"
else "failed"
return statement 4
- 1 By using <- , you’re able to treat your list of candidates like a single candidate.
- 2 The viable function takes a single candidate as an argument.
- 3 Again you’re treating the results of computation on your candidates as operations on a single Candidate.
- 4 When you return the results, you get your list back.
What makes using List as a Monad so interesting is that when you assign your list to a variable using <-, you get to treat it as though it were a single value. The rest of this code looks like it’s operating on one candidate, and yet the final result is the same as applying your logic to every candidate in a list.
When you looked at List as Applicative, you saw some initially confusing examples of nondeterministic computing. For example, if you have two lists and use pure (*) to multiply them with <*>, you get every possible combination of the values from the two lists combined:
GHCi> pure (*) <*> [1 .. 4] <*> [5,6,7] [5,6,7,10,12,14,15,18,21,20,24,28]
You may expect List as Monad to be even more confusing, but it turns out to be surprisingly familiar. The list monad allows you to trivially build complicated lists in an easy-to-program fashion. This is similar to LINQ in C# or list comprehensions in Python and other languages. It turns out there’s even a way to further simplify do-notation for lists that makes generating lists even easier.
What’s the simplest way to create a list of the square of every odd number less than 20?
32.1. Building lists with the list monad
The main use of the list monad is to quickly generate lists. Figure 32.1 shows an example of using the list monad to create a list of powers of 2.
In GHCi, you can use this to create the first 10 powers of 2:
GHCi> powersOfTwo 10 [2,4,8,16,32,64,128,256,512,1024]
Notice that in this definition you can treat the entire list as a single value and the results are as you’d expect. You could easily solve this with map, as you would have in unit 1:
powersOfTwoMap :: Int -> [Int] powersOfTwoMap n = map (x -> 2^x) [1 .. n]
Figure 32.1. Generating lists by thinking of List as a Monad
But in this case, you’re thinking of a list as a list data structure, not abstracting out the context of the list. For this case, the version using map is probably much easier to write and read. But as you generate more complicated lists, being able to focus on how you’d transform a single value can be helpful. Here are some more examples of generating lists with do-notation.
You can combine two lists easily. Suppose you want powers of 2 and 3 as n pairs.
Listing 32.2. Making a list of pairs by using do-notation
powersOfTwoAndThree :: Int -> [(Int,Int)] powersOfTwoAndThree n = do value <- [1 .. n] 1 let powersOfTwo = 2^value 2 let powersOfThree = 3^value 3 return (powersOfTwo,powersOfThree) 4
- 1 Again, you’re treating a list as a single value.
- 2 powersOfTwo is a single value representing a list of powers of 2.
- 3 powersOfThree is a single value representing a list of powers of 3.
- 4 When you return this single pair, it’s actually a list of pairs.
Now you have a list for pairs of powers of 2 and powers of 3:
GHCi> powersOfTwoAndThree 5 [(2,3),(4,9),(8,27),(16,81),(32,243)]
In the preceding example, you used one list, value, to generate your powers of 2. If you make two lists and combine them into pairs the same way, you get different results. Here’s a function that will generate all possible combinations of odd and even numbers up to n:
allEvenOdds :: Int -> [(Int,Int)] allEvenOdds n = do evenValue <- [2,4 .. n] 1 oddValue <- [1,3 .. n] 2 return (evenValue,oddValue) 3
- 1 evenValue is a single value representing a list.
- 2 oddValue is another single value representing a list.
- 3 Because evenValue and oddValue were created with <-, this pair represents all possible pairs from the two values.
As you can see in GHCi, you don’t get a list of size n, but rather all possible combinations of even and odd values:
GHCi> allEvenOdds 5 [(2,1),(2,3),(2,5),(4,1),(4,3),(4,5)] GHCi> allEvenOdds 6 [(2,1),(2,3),(2,5),(4,1),(4,3),(4,5),(6,1),(6,3),(6,5)]
Use do-notation to generate pairs of numbers up to 10 and their squares.
32.1.1. The guard function
Another useful trick is to filter lists. Again you could use filter, but when working with monads, you’d like to be able to reason about a value outside its context. In Control.Monad, a function called guard allows you to filter your values in a list. You have to import Control.Monad to use guard. Here’s a method of generating even numbers by using guard:
evensGuard :: Int -> [Int] evensGuard n = do value <- [1 .. n] guard(even value) 1 return value
- 1 guard filters out all the values that don’t satisfy your test.
Although do-notation makes it easy to generate arbitrarily complex lists by using the methods of Monad, there’s a more familiar interface for this.
Write filter by using guard and do-notation.
guardFilter :: (a -> Bool) -> [a] -> [a] guardFilter test vals = do val <- vals guard(test val) return val
If you look at guard’s type signature, you find that it’s a strange function. Most notably, it has a type class constraint you haven’t seen before:
guard :: Alternative f => Bool -> f()
The Alternative type class is a subclass of Applicative (meaning all instances of Alternative must be instances of Applicative). But, unlike Applicative, Alternative isn’t a superclass of Monad; not all Monads are instances of Alternative. For the guard function, the key method of Alternative is empty, which works exactly like mempty from Monoid. Both List and Maybe are instances of Alternative. List’s empty value is [], and Maybe’s is Nothing. IO, however, isn’t an instance of Alternative. You can’t use guard with IO types.
When you first encounter guard, it might seem like magic. Surely, there must be some stateful mischief going on behind the scenes! Surprisingly, guard is a completely pure function. It’s far beyond the scope of this book, but if you feel comfortable with Monads, revisit guard and see whether you can implement it yourself. To understand guard, it helps tremendously to translate from do-notation back to >>=, >>, and lambdas. Learning about guard will also teach you a lot about the subtleties of >>. Again, this isn’t a particularly useful exercise for beginners, but highly recommended after you’re comfortable working with Monads.
32.2. List comprehensions
If you’re a Python developer, you likely find this method of generating lists a bit verbose. Python uses a special syntax to generate lists, called list comprehensions. Here’s a Python list comprehension to generate powers of 2:
Python> [n**2 for n in range(10)] [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
Python’s list comprehensions also allow you to filter a list on a condition. Here’s a list of squares that are even:
Python> [n**2 for n in range(10) if n**2 % 2 == 0] [0, 4, 16, 36, 64]
Because you’ve been playing with do-notation and lists, this should look close, though more compact, to what you’ve been doing. Here’s the do-notation version of the last Python list comprehension in Haskell, evenSquares.
Listing 32.3. evenPowersOfTwo emulates Python’s list comprehensions
evenSquares :: [Int] evenSquares = do n <- [0 .. 9] let nSquared = n^2 guard(even nSquared) return nSquared
It may come as a bit of a surprise to any Python programmer, but list comprehensions are just specialized applications of monads! Of course, our Haskell example is significantly more verbose than Python’s. By this point in your journey to learning Haskell, the phrase “Haskell is more verbose than ...” should be surprising. Not to be outdone in terseness, Haskell has a further refinement of do-notation specifically for lists: Haskell’s list comprehensions.
List comprehensions provide an even simpler way of generating lists than do-notation. Figure 32.2 shows how to translate a function, powersOfTwo, from do-notation to a list comprehension.
Figure 32.2. List comprehensions simplify do-notation even further for generating lists.
The conversion is reasonably straightforward; here’s powersOfTwoAndThree converted:
powersOfTwoAndThree :: Int -> [(Int,Int)]
powersOfTwoAndThree n = [(powersOfTwo,powersOfThree)
| value <- [1 .. n]
, let powersOfTwo = 2^value 1
, let powersOfThree = 3^value] 2
- 1 As you can see, this is nearly identical to do-notation, except lines are separated by a commas and the new line is purely optional.
- 2 For clarity, the full variable names are used. Typically, shorter variables are used to keep the comprehension a one-liner if possible.
One thing that makes list comprehensions much easier to work with is that you start with the result and then show how it’s generated. It’s often easier to understand what a list comprehension is doing just by looking at the beginning of it:
allEvenOdds :: Int -> [(Int,Int)]
allEvenOdds n = [(evenValue,oddValue) | evenValue <- [2,4 .. n]
, oddValue <- [1,3 .. n]]
The guard function is completely abstracted out of list comprehensions:
evensGuard :: Int -> [Int] evensGuard n = [ value | value <- [1 .. n], even value]
List comprehensions are a nice way to make working with the list monad even easier. The other great insight here is that if you’ve used them in another language, you already have experience writing monadic code! Despite their prominence in Haskell, nothing prevents monads from existing in other languages that support the basics of functional programming covered in unit 1: first-class functions, lambda expressions, and closures. You could build a primate list comprehension system in any language that supports this. You’d simply have to implement >>=, >>, and return.
Write a list comprehension that takes the following words
["brown","blue","pink","orange"]and capitalizes the first letter, and prepends Mr. in front. (Hint: use Data.Char’s toUpper.)
import Data.Char answer :: [String] answer = ["Mr. " ++ capVal | val <- ["brown","blue","pink","organge","white"] , let capVal = ((x:xs) -> toUpper x:xs) val]
32.3. Monads: much more than just lists
In this unit’s capstone, you’re going to take abstracting operations on lists one step further by creating a SQL-like interface for working with lists. All of this time thinking about the list monad may leave you thinking that monads are all about lists. Don’t forget about unit 4! Even though we didn’t discuss it much, nearly every line of code you wrote in that lesson used the Monad type class.
By the end of this unit, you’ll have taken a deep dive into two ways of thinking in Monads: IO and List. The goal here is to show you how powerful an abstraction the idea of working in a context can be. For IO, you used working in a context to separate stateful, nonpure code necessary for I/O from the rest of your safe, predictable program logic. For lists, you’ve seen how to make generating complex data much easier by using the Monad type class. You’ve also seen many examples of using monads to write programs with Maybe types. This has allowed you to write complex programs dealing with missing values while never having to think about how you’ll handle those missing values. All three of these contexts are extremely different, and yet the Monad type class allows you to think about them the exact same way.
Summary
In this lesson, our objective was to further explain the Monad type class by exploring how List behaves as a member of Monad. It may be surprising for many people learning Haskell to discover that list comprehensions, popular in the Python programming language, are equivalent to Monads. Any list comprehension can be trivially converted to do-notation, and any code using do-notation can be trivially desugared to >>= and lambdas. The amazing thing about the Monad type class is that it allows you to abstract out the logic you might use in a list comprehension and seamlessly apply it to both Maybe types and IO types! Let’s see if you got this.
Use a list comprehension that generates a list of correct calendar dates, given that you know the number of days in each month. For example, it should start with 1 .. 31 for January and be followed by 1 .. 28 for February.
Translate the preceding question into do-notation, and then into Monad methods and lambdas.