Lesson 9. Higher-order functions
After reading lesson 9, you’ll be able to
- Understand higher-order functions
- Use map, filter, and foldl to avoid writing explicitly recursive functions
- Implement many higher-order functions yourself
In the preceding lesson, you saw a wide variety of recursive functions. Although practice makes writing recursive code easier, many functions share the exact same patterns of recursion. Therefore, you can abstract out this recursion into a small number of commonly used functions that don’t require you to think about recursion explicitly. The practical answer to the challenge of writing recursive code is that you usually use these existing functions, which are part of a group of functions referred to as higher-order functions.
A higher-order function is technically any function that takes another function as an argument. Typically, when higher-order functions are mentioned, a specific group of them comes to mind, and nearly all of these are used to abstract away common patterns of recursion. In this lesson, you’ll look at higher-order functions that make writing recursive functions much easier. The true cure for recursive headaches is abstraction!
Here are two functions, add3ToAll and mul3byAll, which add 3 to each member of a list and multiply 3 by each member of the list, respectively:
add3ToAll [] = [] add3ToAll (x:xs) = (3 + x):add3ToAll xs mul3ByAll [] = [] mul3ByAll (x:xs) = (3 * x):mul3ByAll xs
Both functions are easy to write and understand, and they share nearly identical structures. Now imagine a function squareAll, which squares each element in a list. The squareAll function also shares this same basic structure. You can probably think of an endless variety of functions that share this exact same pattern. Can you think of how you’d use first-class functions to rewrite these examples by using a new function that takes in a function as an argument and a list and can be used to define both add3ByAll and mul3ByAll?
9.1. Using map
It’s hard to overstate how important the map function is to functional programming and Haskell. The map function takes another function and a list as arguments and applies that function to each element in the list:
GHCi> map reverse ["dog","cat", "moose"] ["god","tac","esoom"] GHCi> map head ["dog","cat", "moose"] "dcm" GHCi> map (take 4) ["pumpkin","pie","peanut butter"] ["pump","pie","pean"]
A common first impression most programmers have of map is that it’s a cleaner version of a for loop. Compare these two approaches to adding the determiner a to a list of animal names in JavaScript (which supports both map and for loops), as shown in the following listing.
Listing 9.1. JavaScript map example
var animals = ["dog","cat","moose"]
//with a for loops
for(i = 0; i < animals.length; i++){
animals[i] = "a " + animals[i]
}
//with map
var addAnA = function(s){return "a "+s}
animals = animals.map(addAnA)
Even in a language that doesn’t enforce functional programming as strictly as Haskell, map has several advantages. For starters, because you’re passing in a named function, you know exactly what’s happening. Given this trivial example, that’s not a big deal, but the body of a for loop can get complicated. If the function is well named, seeing what’s happening in the code is easy. You can also decide that you later want to change the behavior of your map (say, using an addAThe function), and all you have to do is change an argument.
The readability of the code is additionally improved because map is a specific kind of iteration. You know that you’ll get a new list back that’s exactly the same size as the one you put in. This advantage may not be obvious when you’re new to map and other higher-order functions on lists. As you become more literate in the idioms of functional programming, you’ll begin thinking in terms of how you’re transforming a list rather than the general form of iterating through values that a for loop represents.
9.2. Abstracting away recursion with map
The main reason that you use first-class functions, and therefore have higher-order functions, is so you can abstract out programming patterns. To make this clear, let’s look at how map works. It turns out that map bears only a superficial resemblance to a for loop, and under the hood looks nothing at all like it. To figure out how map works, you’ll take two simple tasks you could solve with map and then write them assuming map didn’t exist (nor first-class functions, for that matter). You’ll take your addAnA behavior from our JavaScript example and another function that squares a list of numbers, squareAll. For clarification, here’s the map behavior you’re trying to re-create:
GHCi> map ("a "++) ["train","plane","boat"]
["a train","a plane","a boat"]
GHCi> map (^2) [1,2,3]
[1,4,9]
You’ll start with addAnA first. Once again, the first question you need to ask is, “What’s your goal state?” Because you’re going straight through the list, you’ll be finished when you hit []. The next question is, “What do you do at the end?” You’re trying to add a to each of the terms in the list, and there are no terms, so it’s sensible to return the empty list. The other hint that you want to return an empty list is that you’re building a list. If your recursive function returns a list, it must somehow end in the empty list. For your goal state, you get a simple definition:
addAnA [] = []
The only other possibility is that there’s a nonempty list. In that case, you want to take the head of the list and apply addAnA to whatever is left:
addAnA (x:xs) = ("a " ++ x):addAnA xs
Do you meet your demand of moving closer to your goal? Yes, because you’re taking the tail of your list, which will eventually lead you to the empty list.
The squareAll function follows a similar pattern. It ends at the empty list, and the only other option is for the argument to be a non-empty list. In the event of a nonempty list, you square the head and continue on your way:
squareAll [] = [] squareAll (x:xs) = x^2:squareAll xs
If you go ahead and remove the concatenating and squaring function, replacing them with an f for any function, you end up with the definition of map!
Listing 9.2. myMap
myMap f [] = [] myMap f (x:xs) = (f x):myMap f xs
If you didn’t have map, you’d end up repeating this pattern of writing a recursive function over and over again. The literal recursion isn’t particularly difficult, but would be much less pleasant to write and read frequently. If you find recursion challenging, the good news is that any pattern of recursion that has been used enough is abstracted out. In practice, you don’t explicitly write out recursive functions that often. But because the common patterns of recursion are already higher-order functions, when you do come across a truly recursive problem, it typically requires careful thought.
9.3. Filtering a list
Another important higher-order function for working with lists is filter. The filter function looks and behaves similarly to map, taking a function and a list as arguments and returning a list. The difference is that the function passed to filter must be passed a function that returns True or False. The filter function works by keeping only the elements of the list that pass the test:
GHCi> filter even [1,2,3,4] [2,4] GHCi> filter (\(x:xs) -> x == 'a') ["apple","banana","avocado"] ["apple","avocado"]
The use of filter is straightforward, and it’s a handy tool to have. The most interesting thing about filter is the pattern of recursion it abstracts out. As with map, the goal of filter is an empty list. What makes filter different is that there are two possible alternatives: a nonempty list in which the first element passes, and a nonempty list in which the first element doesn’t pass. The only difference is that when the test fails, the element isn’t recursively consed to the list.
Listing 9.3. myFilter
myFilter test [] = []
myFilter test (x:xs) = if test x 1
then x:myFilter test xs 2
else myFilter test xs 3
- 1 See whether the head of the list passes the test.
- 2 If it does pass, cons it with filtering the rest of the list.
- 3 Otherwise, continue filtering the rest of the list.
Implement remove, which removes elements that pass the test
remove test [] = []
remove test (x:xs) = if test x
then remove test xs
else x:remove test xs
9.4. Folding a list
The function foldl (the l stands for left, which we’ll explain soon) takes a list and reduces it to a single value. The function takes three arguments: a binary function, an initial value, and a list. The most common use of foldl is to sum a list:
GHCi> foldl (+) 0 [1,2,3,4] 10
foldl is probably the least obvious of the higher-order functions we’ve covered. The way foldl works is to apply the binary argument to the initial value and the head of the list. The result of this function is now the new initial value. Figure 9.1 shows the process.
Figure 9.1. Visualizing foldl (+)
Write the function myProduct, which calculates the product of a list of numbers.
Fold is useful but definitely takes some practice to get used to. You can build a concatAll function that joins all strings in a list:
concatAll xs = foldl (++) "" xs
It’s common to use foldl and map together. For example, you can create sumOfSquares, which squares every value in a list and then takes the sum of it:
sumOfSquares xs = foldl (+) 0 (map (^2) xs)
Perhaps the most remarkable use of foldl is to reverse a list. To do this, you need a helper function named rcons, which will cons elements in the reverse order.
Listing 9.4. myReverse
rcons x y = y:x myReverse xs = foldl rcons [] xs
This is another function worth visualizing to add clarity; see figure 9.2.
Figure 9.2. Visualizing foldl rcons
Note that in this case, the “single” value that foldl returns is another list!
Implementing foldl is a bit trickier than the other functions you’ve seen so far. Once again, your goal state is the empty list, []. But what should you return? Because the initial value will get updated after each call to the binary function, it’ll contain the final value in your computation. When you reach the end of the list, you return the current value for init:
myFoldl f init [] = init
You have only one other alternative: a nonempty list. For this, you pass your initial value and the head of your list to the binary function. This creates your new init value. Then you call myFoldl on the rest of the list by using this new value as your init.
Listing 9.5. myFoldl
myFoldl f init [] = init myFoldl f init (x:xs) = myFoldl f newInit xs where newInit = f init x
True or false: The nongoal step in myFoldl terminates.
True: because you’re always recursing on the rest of the list, it must get smaller until it’s empty (if it’s not infinite).
The question that remains is, why left fold? It turns out that there’s another way to solve this general problem of folding a list of values into a single value. The alterative to foldl is foldr; the r stands for right. If you look at the definition of myFoldr, you can see how it differs.
Listing 9.6. myFoldr
myFoldr f init [] = init myFoldr f init (x:xs) = f x rightResult where rightResult = myFoldr f init xs
The reason we call it a right fold is that there are two arguments in a binary function: a left argument and a right argument. The left fold compacts the list into the left argument, and the right fold into the right argument.
Both performance and computational differences exist between foldl and foldr. At this stage in learning, it’s important to know that these functions give different answers if the order of the application matters. For addition, the order doesn’t matter, so these functions behave the same:
GHCi> foldl (+) 0 [1,2,3,4] 10 GHCi> foldr (+) 0 [1,2,3,4] 10
But for subtraction, order does matter:
GHCi> foldl (-) 0 [1,2,3,4] -10 GHCi> foldr (-) 0 [1,2,3,4] -2
When learning Haskell, foldl is preferable for folding lists because its behavior is more intuitive. Understanding the difference between foldl and foldr is a good sign that you’ve mastered recursion.
The family of fold functions are, undoubtedly, the trickiest of the higher-order functions introduced here. There’s another useful fold function named foldl' (note the tick mark) found in the Data.List module. Here’s a list of advice for when to use each fold:
- foldl is the most intuitive behaving of the folds, but it usually has terrible performance and can’t be used on infinite lists.
- foldl' is a nonlazy version of foldl that’s often much more efficient.
- foldr is often more efficient than foldl and is the only fold that works on infinite lists.
When learning Haskell, there’s no need to immediately master these various types of folds. You’ll likely run into an issue with foldl as you write more-sophisticated Haskell code.
Summary
In this lesson, our objective was to introduce you to a family of functions that make working with recursion much easier. Many recursive problems can be solved with map, filter, and foldl. When encountering a recursive problem, the first question you should ask is whether you can solve it with one of these three functions. Let’s see if you got this.
Use filter and length to re-create the elem function.
Your isPalindrome function from lesson 6 doesn’t handle sentences with spaces or capitals. Use map and filter to make sure the phrase “A man a plan a canal Panama” is recognized as a palindrome.
In mathematics, the harmonic series is the sum of 1/1 + 1/2 + 1/3 + 1/4 .... Write a function harmonic that takes an argument n and calculates the sum of the series to n. Make sure to use lazy evaluation.