Chapter 12. Higher-Order Functions
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 a parameter. 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 function argument 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 = ceil _
This code sets num to 3.14 and fun to the ceil function.
The _ behind the ceil function indicates that you really meant the function, and you didn’t just forget to supply the arguments.
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.
Note
Technically, the _ turns the ceil method into a function. In Scala, you cannot manipulate methods, only functions. The type of the function is (Double) => Double, with an arrow. In contrast, the type of the ceil method is (Double)Double, without an arrow. There is no way for you to work with such a type, but you will find it in compiler and REPL messages.
The _ suffix is not necessary when you use a method name in a context where a function is expected. For example, the following is legal:
val f: (Double) => Double = ceil // No underscore needed
Note
The ceil method is a method of the scala.math package object. If you have a method from a class, the syntax for turning it into a function is slightly different:
val f = (_: String).charAt(_: Int)
// A function (String, Int) => Char
Alternatively, you can specify the type of the function instead of the parameter types:
val f: (String, Int) => Char = _.charAt(_)
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.0
As 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 parameters.
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 * x
This function multiplies its argument by 3.
Of course, you can store this function in a variable:
val triple = (x: Double) => 3 * x
That’s just as if you had used a def:
def triple(x: Double) = 3 * x
But 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
Anything defined with def (in the REPL or a class or object) is a method, not a function:
scala> def triple(x: Double) = 3 * x
triple: (x: Double)Double
Note the method type (x: Double)Double. In contrast, a function definition has a function type:
scala> val triple = (x: Double) => 3 * x
triple: Double => Double
12.3 Functions with Function Parameters
In this section, you will see how to implement a function that takes another function as a parameter. 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.0
valueAtOneQuarter(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) => resultType
The 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) => Double
Since 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 * x
For 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) // 100
The mulBy function has a parameter of type Double, and it returns a function of type (Double) => Double. Therefore, its type is
(Double) => ((Double) => Double)
12.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.75
Since 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 parameter:
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 types
val fun = 3 * (_: Double) // OK
val 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).
Note
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, 8
Of 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 * 9
or, 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, “Functions with Function Parameters,” on page 160.
def mulBy(factor : Double) = (x : Double) => factor * x
Consider these calls:
val triple = mulBy(3)
val half = mulBy(0.5)
println(s"${triple(14)} ${half(14)}") // Prints 42 7
Let’s look at them in slow motion.
1. The first call to mulBy sets the parameter variable factor to 3. That variable is referenced in the body of the function (x : Double) => factor * x, which is stored in triple. Then the parameter variable factor is popped off the runtime stack.
2. Next, mulBy is called again, now with factor set to 0.5. That variable is referenced in the body of the function (x : Double) => factor * x, which is stored in half.
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 SAM Conversions
In Scala, you pass a function as a parameter whenever you want to tell another function what action to carry out. Prior to Java 8, this was not possible in Java without defining a class and a method for the action. For example, to implement a button callback, one had to use this Scala code (or its Java equivalent):
var counter = 0
val button = new JButton("Increment")
button.addActionListener(new ActionListener {
override def actionPerformed(event: ActionEvent) {
counter += 1
}
})
In Java 8, it is possible to specify such actions with lambda expressions, which are closely related to functions in Scala. Fortunately, that means that as of Scala 2.12, one can pass Scala functions to Java code expecting a “SAM interface”—that is, any Java interface with a single abstract method. (Such interfaces are officially called functional interfaces in Java.)
Simply pass the function to the addActionListener method, like this:
button.addActionListener(event => counter += 1)
Note that the conversion from a Scala function to a Java SAM interface only works for function literals, not for variables holding functions. The following does not work:
val listener = (event: ActionListener) => println(counter)
button.addActionListener(listener)
// Cannot convert a nonliteral function to a Java SAM interface
The simplest remedy is to declare the variable holding the function as a Java SAM 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) System.exit(0)
button.addActionListener(exit(_))
12.8 Currying
Currying (named after logician Haskell Brooks Curry) is the process of turning a function that takes two arguments into a function that takes one argument. That function returns a function that consumes the second argument.
Huh? Let’s look at an example. This function takes two arguments:
val mul = (x: Int, y: Int) => x * y
This function takes one argument, yielding a function that takes one argument:
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 mulOneAtATime(x: Int)(y: Int) = x * y
Note
Recall that anything defined with def (in the REPL or a class or object) is a method, not a function. When defining curried methods with def, you can use multiple parentheses:
scala> def mulOneAtATime(x: Int)(y: Int) = x * y
mulOneAtATime: (x: Int)(y: Int)Int
Note the method type (x: Int)(y: Int)Int. In contrast, when you define a function, you must use multiple arrows, not multiple parentheses:
scala> val mulOneAtATime = (x: Int) => (y: Int) => x * y
mulOneAtATime: Int => (Int => Int)
As 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("Hello", "World")
val b = Array("hello", "world")
a.corresponds(b)(_.equalsIgnoreCase(_))
Note that the function _.equalsIgnoreCase(_) 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): Boolean
The 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 a String sequence. Therefore, the predicate is expected to have type (String, String) => Boolean. With that information, the compiler can accept _.equalsIgnoreCase(_) as a shortcut for (a: String, b: String) => a.equalsIgnoreCase(b).
12.9 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) {
new Thread {
override def run() { 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) {
new Thread {
override def run() {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) {
if (!condition) {
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 arguments. That function is passed as a parameter.
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.10 The return Expression
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.
However, you can use return to return a value from an anonymous function to an enclosing named function. This is useful in 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) return i
i += 1
}
return -1
}
Here, the anonymous function { if (str(i) == ch) return i; i += 1 } is passed to until. When the return expression is executed, the enclosing named function indexOf terminates and returns the given value.
If you use return inside a named function, you need to specify its return type. For example, in the indexOf function above, the compiler was not able to infer that it returns an Int.
The control flow is achieved with a special exception that is thrown by the return expression in the anonymous function, passed out of the until function, and caught in the indexOf function.
Caution
If the exception is caught in a try block, before it is delivered to the named function, then the 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. It’s easy to get a sequence of pairs, for example:
val pairs = (1 to 10) zip (11 to 20)
Now, suppose you want to do something with such a sequence—say, add up the values. But you can’t do
pairs.map(_ + _)
The function _ + _ takes two Int parameters, not an (Int, Int) pair. Write a function adjustToPair that receives a function of type (Int, Int) => Int and returns the equivalent function that operates on a pair. For example, adjustToPair(_ * _)((6, 7)) is 42.
Then use this function in conjunction with map to compute the sums of the elements in pairs.
8. In Section 12.8, “Currying,” on page 164, 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.
9. Implement corresponds without currying. Then try the call from the preceding exercise. What problem do you encounter?
10. 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?