Chapter 12. Higher-Order Functions
Topics in This Chapter L1
Scala mixes object orientation with functional features. In a functional programming language, functions are first-class citizens that can be passed around and manipulated just like any other data types. This is very useful whenever you want to pass some action detail to an algorithm. In a functional language, you just wrap that detail into a function that you pass as an argument. In this chapter, you will see how to be productive with functions that use or return functions.
Highlights of the chapter include:
Functions are “first-class citizens” in Scala, just like numbers.
You can create anonymous functions, usually to give them to other functions.
A parameter that is a function specifies behavior that should be executed later.
Many collection methods take function parameters, applying a function to the values of the collection.
There are syntax shortcuts that allow you to express function parameters in a way that is short and easy to read.
You can create functions that operate on blocks of code and look much like the built-in control statements.
12.1 Functions as Values
In Scala, a function is a first-class citizen, just like a number. You can store a function in a variable:
import scala.math.*
val num = 3.14
val fun = ceilThis code sets num to 3.14 and fun to the ceil function.
When you try this code in the REPL, the type of num is, not surprisingly, Double. The type of fun is reported as Double => Double—that is, a function receiving and returning a Double.
What can you do with a function? Two things:
Call it.
Pass it around, by storing it in a variable or giving it to a function as a parameter.
Here is how to call the function stored in fun:
fun(num) // 4.0As you can see, the normal function call syntax is used. The only difference is that fun is a variable containing a function, not a fixed function.
Here is how you can give fun to another function:
Array(3.14, 1.42, 2.0).map(fun) // Array(4.0, 2.0, 2.0)The map method accepts a function, applies it to all values in an array, and returns an array with the function values. In this chapter, you will see many other methods that accept functions as arguments.
12.2 Anonymous Functions
In Scala, you don’t have to give a name to each function, just like you don’t have to give a name to each number. Here is an anonymous function:
(x: Double) => 3 * xThis function multiplies its argument by 3.
Of course, you can store this function in a variable:
val triple = (x: Double) => 3 * xThat’s just as if you had used a def:
def triple(x: Double) = 3 * xBut you don’t have to name the function. You can just pass it to another function:
Array(3.14, 1.42, 2.0).map((x: Double) => 3 * x)
// Array(9.42, 4.26, 6.0)Here, we tell the map method: “Multiply each element by 3.”
Note
If you prefer, you can enclose the function argument in braces instead of parentheses, for example:
Array(3.14, 1.42, 2.0).map{ (x: Double) => 3 * x }This is more common when a method is used in infix notation (without the dot).
Array(3.14, 1.42, 2.0) map { (x: Double) => 3 * x } Note
As noted in Chapter 2, some people consider anything that is declared with def to be a method. However, in this book, we use a conceptually cleaner mental model. Methods are invoked on objects. They are members of classes, traits, or objects. Top-level and block-level def statements declare functions.
In those cases, you cannot tell whether def declares anything other than a function. The expression triple is indistinguishable from the function (x: Double) => 3 * x. (This conversion is called eta expansion, using terminology from the lambda calculus.)
Caution
There is only one exception to eta expansion—when there are no parameters:
def heads() = scala.math.random() < 0.5For arcane reasons, heads is a syntax error. The function is heads _, and it is invoked as heads().
12.3 Parameters That Are Functions
In this section, you will see how to implement a function whose parameter is another function. Here is an example:
def valueAtOneQuarter(f: (Double) => Double) = f(0.25)Note that the parameter can be any function receiving and returning a Double. The valueAtOneQuarter function computes the value of that function at 0.25.
For example,
valueAtOneQuarter(ceil) // 1.0valueAtOneQuarter(sqrt) // 0.5(because 0.5 × 0.5 = 0.25)
What is the type of valueAtOneQuarter? It is a function with one parameter, so its type is written as
(parameterType) => resultTypeThe resultType is clearly Double, and the parameterType is already given in the function header as (Double) => Double. Therefore, the type of valueAtOneQuarter is
((Double) => Double) => DoubleSince valueAtOneQuarter is a function that receives a function, it is called a higher-order function.
A higher-order function can also produce a function. Here is a simple example:
def mulBy(factor : Double) = (x : Double) => factor * xFor example, mulBy(3) returns the function (x : Double) => 3 * x which you have seen in the preceding section. The power of mulBy is that it can deliver functions that multiply by any amount:
val quintuple = mulBy(5)
quintuple(20) // 100The mulBy function has a parameter of type Double, and it returns a function of type (Double) => Double. Therefore, its type is
(Double) => ((Double) => Double)When written without parentheses, the type is
Double => Double => Double12.4 Parameter Inference
When you pass an anonymous function to another function or method, Scala helps you out by deducing types when possible. For example, you don’t have to write
valueAtOneQuarter((x: Double) => 3 * x) // 0.75Since the valueAtOneQuarter method knows that you will pass in a (Double) => Double function, you can just write
valueAtOneQuarter((x) => 3 * x)As a special bonus, for a function that has just one parameter, you can omit the () around the argument:
valueAtOneQuarter(x => 3 * x)It gets better. If a parameter occurs only once on the right-hand side of the =>, you can replace it with an underscore:
valueAtOneQuarter(3 * _)This is the ultimate in comfort, and it is also pretty easy to read: a function that multiplies something by 3.
Keep in mind that these shortcuts only work when the parameter types are known.
val fun = 3 * _ // Error: Can’t infer typesYou can specify a type for the anonymous parameter or for the variable:
3 * (_: Double) //OKval fun: (Double) => Double = 3 * _ //OK because we specified the type for fun
Of course, the last definition is contrived. But it shows what happens when a function is passed to a parameter (which has just such a type).
Tip
Specifying the type of _ is useful for turning methods into functions. For example, (_: String).length is a function String => Int, and (_: String).substring(_:Int, _: Int) is a function (String, Int, Int) => String.
12.5 Useful Higher-Order Functions
A good way of becoming comfortable with higher-order functions is to practice with some common (and obviously useful) methods in the Scala collections library that take function parameters.
You have seen map, which applies a function to all elements of a collection and returns the result. Here is a quick way of producing a collection containing 0.1, 0.2,..., 0.9:
(1 to 9).map(0.1 * _) Note
There is a general principle at work. If you want a sequence of values, see if you can transform it from a simpler one.
Try this to print a triangle:
(1 to 9).map("*" * _).foreach(println _)The result is
*
**
***
****
*****
******
*******
********
*********Here, we also use foreach, which is like map except that its function doesn’t return a value. The foreach method simply applies the function to each argument.
The filter method yields all elements that match a particular condition. For example, here’s how to get only the even numbers in a sequence:
(1 to 9).filter(_ % 2 == 0) // 2, 4, 6, 8Of course, that’s not the most efficient way of getting this result 
.
The reduceLeft method takes a binary function—that is, a function with two parameters—and applies it to all elements of a sequence, going from left to right. For example,
(1 to 9).reduceLeft(_ * _)is
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9or, strictly speaking,
(...((1 * 2) * 3) * ... * 9)Note the compact form of the multiplication function: _ * _. Each underscore denotes a separate parameter.
You also need a binary function for sorting. For example,
"Mary had a little lamb".split(" ").sortWith(_.length < _.length)yields an array that is sorted by increasing length: Array("a", "had", "Mary", "lamb", "little").
12.6 Closures
In Scala, you can define a function inside any scope: in a package, in a class, or even inside another function or method. In the body of a function, you can access any variables from an enclosing scope. That may not sound so remarkable, but note that your function may be called when the variable is no longer in scope.
Here is an example: the mulBy function from Section 12.3, “Parameters That Are Functions,” on page 171.
def mulBy(factor : Double) = (x : Double) => factor * xConsider these calls:
val triple = mulBy(3)val half = mulBy(0.5)println(s"${triple(14)} ${half(14)}") //Prints 42.0 7.0
Let’s look at them in slow motion.
The first call to
mulBysets the parameter variablefactorto3. That variable is referenced in the body of the function(x : Double) => factor * x, which is stored intriple. Then the parameter variablefactoris popped off the runtime stack.Next,
mulByis called again, now withfactorset to0.5. That variable is referenced in the body of the function(x : Double) => factor * x, which is stored inhalf.
Each of the returned functions has its own setting for factor.
Such a function is called a closure. A closure consists of code together with the definitions of any nonlocal variables that the code uses.
These functions are actually implemented as objects of a class, with an instance variable factor and an apply method that contains the body of the function.
It doesn’t really matter how a closure is implemented. It is the job of the Scala compiler to ensure that your functions can access nonlocal variables.
Note
Closures aren’t difficult or surprising if they are a natural part of the language. Many modern languages, such as JavaScript, Ruby, and Python, support closures. Java, as of version 8, has closures in the form of lambda expressions.
12.7 Interoperability with Lambda Expressions
In Scala, you pass a function as a parameter whenever you want to tell another function what action to carry out. In Java, you use a lambda expression:
var button = new JButton("Increment"); // This is Java
button.addActionListener(event -> counter++);In order to pass a lambda expression, the parameter type must be a “functional interface”—that is, any Java interface with a single abstract method.
You can pass a Scala function to a Java functional interface:
val button = JButton("Increment")
button.addActionListener(event => counter += 1)Note that the conversion from a Scala function to a Java functional interface only works for function literals, not for variables holding functions. The following does not work:
val listener = (event: ActionEvent) => println(counter)button.addActionListener(listener)//Cannot convert a nonliteral function to a Java functional interface
The simplest remedy is to declare the variable holding the function as a Java functional interface:
val listener: ActionListener = event => println(counter)button.addActionListener(listener) //OK
Alternatively, you can turn a function variable into a literal expression:
val exit = (event: ActionEvent) => if counter > 9 then System.exit(0)
button.addActionListener(exit(_))12.8 Currying
Currying (named after logician Haskell Brooks Curry) is the process of turning a function with two parameters into a function with one parameter. That function returns a function that consumes the second argument.
Huh? Let’s look at an example. This function has two parameters:
val mul = (x: Int, y: Int) => x * yThis function has one parameter, yielding a function with one parameter:
val mulOneAtATime = (x: Int) => ((y: Int) => x * y)To multiply two numbers, you call
mulOneAtATime(6)(7)Strictly speaking, the result of mulOneAtATime(6) is the function (y: Int) => 6 * y. That function is applied to 7, yielding 42.
When you use def, there is a shortcut for defining such curried methods in Scala:
def divOneAtATime(x: Int)(y: Int) = x / yAs you can see, multiple parameters are just a frill, not an essential feature of a programming language. That’s an amusing theoretical insight, but it has one practical use in Scala. Sometimes, you can use currying for a method parameter so that the type inferencer has more information.
Here is a typical example. The corresponds method can compare whether two sequences are the same under some comparison criterion. For example,
val a = Array("Mary", "had", "a", "little", "lamb")
val b = Array(4, 3, 1, 6, 5)
a.corresponds(b)(_.length == _)Note that the function _.length == _ is passed as a curried parameter, in a separate set of (...). When you look into the Scaladoc, you will see that corresponds is declared as
def corresponds[B](that: Seq[B])(p: (A, B) => Boolean): BooleanThe that sequence and the predicate function p are separate curried parameters. The type inferencer can figure out what B is from the type of that, and then it can use that information when analyzing the function that is passed for p.
In our example, that is an Int sequence. Therefore, the predicate is expected to have type (String, Int) => Boolean. With that information, the compiler can accept _.length == _ as a shortcut for (a: String, b: Int) => a.length == b.
12.9 Methods for Composing, Currying, and Tupling
A unary function is a function with one parameter. All unary functions are instances of the Function1 trait. That trait defines a method for composing two unary functions—that is, executing one and then passing the result to the other.
Suppose we want to be sure that we don’t compute square roots of negative values. Then we can compose the square root function with the absolute value function:
val sqrt = scala.math.sqrtval fabs: Double => Double = scala.math.abs//Need the type because abs is overloadedval f = sqrt compose fabs //Infix notation; could also write sqrt.compose(fabs)f(-9) //Yields sqrt(fabs(-9)) or 3
Note that the second function is executed first, because functions are applied right to left. If you find that unnatural, use the andThen method instead:
val g = fabs andThen sqrt // The same as sqrt compose fabsFunctions with more than one parameter have a curried method, producing the curried version of a function.
val fmax : (Double, Double) => Double = scala.math.max
// Need the type because max is overloaded
fmax.curried // Has type Double => Double => Double
val h = fmax.curried(0)The function h has one parameter, and h(x) = fmax.curried(0)(x) = fmax(0, x). Positive arguments are returned, and negative arguments yield zero.
The tupled method turns a function with more than one parameter into a unary function receiving a tuple.
val k = mul.tupled // Has type ((Int, Int)) => IntWhen calling k, you supply a pair whose components are passed to mul. For example, k((6, 7)) is 42.
This sounds abstract, but here is a practical use. Let’s say you have two arrays, holding the first and second arguments.
val xs = Array(1, 7, 2, 9)
val ys = Array(1000, 100, 10, 1)Now we want to pass corresponding elements to a binary function such as mul. An elegant solution is to zip the arrays, and then apply the tupled function to the pairs:
xs.zip(ys).map(mul.tupled) // Yields Array(1000, 700, 20, 9) Note
If you pass a function literal, then you don’t need to call tupled. The elements of the zipped array are untupled, and the components are passed to the function:
xs.zip(ys).map(_ * _) // The tuple components are passed to the function12.10 Control Abstractions
In Scala, one can model a sequence of statements as a function with no parameters or return value. For example, here is a function that runs some code in a thread:
def runInThread(block: () => Unit) =
Thread(() => block()).start()The code is given as a function of type () => Unit. However, when you call this function, you need to supply an unsightly () =>:
runInThread { () => println("Hi"); Thread.sleep(10000); println("Bye") }To avoid the () => in the call, use the call by name notation: Omit the (), but not the =>, in the parameter declaration and in the call to the parameter function:
def runInThread(block: => Unit) =
Thread(() => block).start()Then the call becomes simply
runInThread { println("Hi"); Thread.sleep(10000); println("Bye") }This looks pretty nice. Scala programmers can build control abstractions: functions that look like language keywords. For example, we can implement a function that is used exactly as a while statement. Or, we can innovate a bit and define an until statement that works like while, but with an inverted condition:
def until(condition: => Boolean)(block: => Unit): Unit =
if !condition then
block
until(condition)(block)Here is how you use until:
var x = 10
until (x == 0) {
x -= 1
println(x)
}The technical term for such a function parameter is a call-by-name parameter. Unlike a regular (or call-by-value) parameter, the parameter expression is not evaluated when the function is called. After all, we don’t want x == 0 to evaluate to false in the call to until. Instead, the expression becomes the body of a function with no parameters. That function is passed to until.
Look carefully at the until function definition. Note that it is curried: It first consumes the condition, then the block as a second parameter. Without currying, the call would look like this:
until(x == 0, { ... })which wouldn’t be as pretty.
12.11 Nonlocal Returns
In Scala, you don’t use a return statement to return function values. The return value of a function is simply the value of the function body.
A return statement would be particularly problematic with control abstractions. For example, consider this function:
def indexOf(str: String, ch: Char): Int =
var i = 0
until (i == str.length) {
if str(i) == ch then return i // No longer valid in Scala
i += 1
}
-1Does return return from the anonymous function { if str(i) == ch then return i; i += 1 } that is passed to until, or from the indexOf function? Here, we want the latter. Earlier versions of Scala had a return expression that threw an exception to the enclosing named function. That fragile mechanism has been replaced with the returning control abstraction:
import scala.util.control.NonLocalReturns.*
def indexOf(str: String, ch: Char): Int =
returning {
var i = 0
until (i == str.length) {
if str(i) == ch then throwReturn(i)
i += 1
}
-1
} Caution
If the exception is caught in a try block, before it is delivered to the returning function, then the thrown value will not be returned.
Exercises
1. Write a function values(fun: (Int) => Int, low: Int, high: Int) that yields a collection of function inputs and outputs in a given range. For example, values(x => x * x, -5, 5) should produce a collection of pairs (-5, 25), (-4, 16), (-3, 9),..., (5, 25).
2. How do you get the largest element of an array with reduceLeft?
3. Implement the factorial function using to and reduceLeft, without a loop or recursion.
4. The previous implementation needed a special case when n < 1. Show how you can avoid this with foldLeft. (Look at the Scaladoc for foldLeft. It’s like reduceLeft, except that the first value in the chain of combined values is supplied in the call.)
5. Write a function largest(fun: (Int) => Int, inputs: Seq[Int]) that yields the largest value of a function within a given sequence of inputs. For example, largest(x => 10 * x - x * x, 1 to 10) should return 25. Don’t use a loop or recursion.
6. Modify the previous function to return the input at which the output is largest. For example, largestAt(x => 10 * x - x * x, 1 to 10) should return 5. Don’t use a loop or recursion.
7. Write a function that composes two functions of type Double => Option[Double], yielding another function of the same type. The composition should yield None if either function does. For example,
def f(x: Double) = if x != 1 then Some(1 / (x - 1)) else Nonedef g(x: Double) = if x >= 0 then Some(sqrt(x)) else Noneval h = compose(g, f) //h(x) should be g(f(x))
Then h(2) is Some(1), and h(1) and h(0) are None.
8. Section 12.9, “Methods for Composing, Currying, and Tupling,” on page 177 covers the composing, currying, and tupling methods that all functions have. Implement these from scratch, as functions that operate on integer functions. For example, tupling(mul) returns a function ((Int, Int)) => Int, and tupling(mul)((6, 7)) is 42.
9. What does the curried method do for a method with more than two parameters?
10. In Section 12.8, “Currying,” on page 176, you saw the corresponds method used with two arrays of strings. Make a call to corresponds that checks whether the elements in an array of strings have the lengths given in an array of integers.
11. Implement corresponds without currying. Then try the call from the preceding exercise. What problem do you encounter?
12. Implement an unless control abstraction that works just like if, but with an inverted condition. Does the first parameter need to be a call-by-name parameter? Do you need currying?