Higher-Order Functions
Using higher-order functions, computations can be parameterized by other computations in powerful ways.
This chapter is from the book
This chapter is from the book
This chapter is from the book
It is natural for a programming paradigm that centers on functions to treat them as first-class citizens. In functional programming, functions are values and can be stored in variables and passed as arguments. Functions that consume or produce other functions are said to be higher-order functions. Using higher-order functions, computations can be parameterized by other computations in powerful ways.
9.1 Functions as Values
Previous chapters have shown how pure functions from immutable values to immutable values can be used as building programming blocks, and how complex computations can be achieved by composing functions, including composing a function with itself through recursion. Although pure functions, immutability, and recursion are essential concepts, many would argue that the distinctive characteristic of a functional programming style is the use of functions as values.
To help motivate the benefits of functions as values, consider this first illustration. Suppose you need to search for a value in a list. You can implement such a lookup in a recursive function, similar to function contains from Chapter 7:
Scala
Listing 9.1: List lookup for a specific target.
def find[A](list: List[A], target: A): Option[A] = list match case Nil => None case h :: t => if h == target then Some(h) else find(t, target)
This function checks whether the head of a non-empty list equals the target and, if not, keeps searching in the tail of the list. It returns an option to allow for cases where the target value is not found. You can use find to look for specific values in a list, like a list of temperatures:
Scala
val temps = List(88, 91, 78, 69, 100, 98, 70) find(temps, 78) // Some(78) find(temps, 79) // None
A limitation of this function, however, is that you can only search for a target if you already have a value equal to that target. For instance, you cannot search a list of temperatures for a value greater than 90. Of course, you can easily write another function for that:
Scala
def findGreaterThan90(list: List[Int]): Option[Int] = list match case Nil => None case h :: t => if h > 90 then Some(h) else findGreaterThan90(t) findGreaterThan90(temps) // Some(91)
But what if you need to search for a temperature greater than 80 instead? You can write another function, in which an integer argument replaces the hardcoded value 90:
Scala
def findGreaterThan(list: List[Int], bound: Int): Option[Int] = list match case Nil => None case h :: t => if h > bound then Some(h) else findGreaterThan(t, bound) findGreaterThan(temps, 80) // Some(88)
This is better, but the new function still cannot be used to search for a temperature less than 90, or for a string that ends with "a", or for a project with identity 12345.
You will notice that functions find, findGreaterThan90, and findGreaterThan are strikingly similar. The algorithm is the same in all three cases. The only part of the implementation that changes is the test in the if-then-else, which is h == target in the first function, h > 90 in the next, and h > bound in the third.
It would be nice to write a generic function find parameterized by a search criterion. Criteria such as “to be greater than 90” or “to end with "a"” or “to have identity 12345” could then be used as arguments. To implement the if-then-else part of this function, you would apply the search criterion to the head of the list to produce a Boolean value. In other words, you need the search criterion to be a function from A to Boolean.
Such a function find can be written. It takes another function as an argument, named test:
Scala
Listing 9.2: Recursive implementation of higher-order function find.
def find[A](list: List[A], test: A => Boolean): Option[A] = list match case Nil => None case h :: t => if test(h) then Some(h) else find(t, test)
The type of argument test is A => Boolean, which in Scala denotes functions from A to Boolean. As a function, test is applied to the head of the list h (of type A), and produces a value of type Boolean (used as the if condition).
You can use this new function find to search a list of temperatures for a value greater than 90 by first defining the “greater than 90” search criterion as a function:
Scala
def greaterThan90(x: Int): Boolean = x > 90 find(temps, greaterThan90) // Some(91)
In this last expression, you do not invoke function greaterThan90 on an integer argument. Instead, you use the function itself as an argument to find. To search for a project with identity 12345, simply define a different search criterion:
Scala
def hasID12345(project: Project): Boolean = project.id == 12345L find(projects, hasID12345) // project with identity 12345
Because it takes a function as an argument, find is said to be a higher-order function. Functional programming libraries define many standard higher-order functions, some of which are discussed in Chapter 10. In particular, a method find is already defined on Scala’s List type. The two searches in the preceding examples can be written as follows:
Scala
temps.find(greaterThan90) projects.find(hasID12345)
From now on, code examples in this chapter use the standard method find instead of the earlier user-defined function.
Method find is a higher-order function because it takes another function as an argument. A function can also be higher-order by returning a value that is a function. For example, instead of implementing greaterThan90, you can define a function that builds a search criterion to look for temperatures greater than a given bound:
Scala
Listing 9.3: Example of a function that returns a function; see also Lis. 9.4 and 9.5.
def greaterThan(bound: Int): Int => Boolean = def greaterThanBound(x: Int): Boolean = x > bound greaterThanBound
Function greaterThan works by first defining a function greaterThanBound. This function is not applied to anything but simply returned as a value. Note that greaterThan has return type Int => Boolean, which denotes functions from integers to Booleans. Given a lower bound b, the expression greaterThan(b) is a function, which tests whether an integer is greater than b. It can be used as an argument to higher-order method find:
Scala
temps.find(greaterThan(90)) temps.find(greaterThan(80))
In a similar fashion, you can define a function to generate search criteria for projects:
Scala
def hasID(identity: Long): Project => Boolean = def hasGivenID(project: Project): Boolean = project.id == identity hasGivenID projects.find(hasID(12345L)) projects.find(hasID(54321L))