Higher-order functions and function literals

Here is a function that computes the sum of the integers from \(a\) to \(b\):

def sumInt(a: Int, b: Int): Int = {
  var s = 0
  for (i <- a to b)
    s += i
  s
}

And here is code to compute the sum of the cubes of the integers from \(a\) to \(b\):

def cube(x: Int): Int = x * x * x

def sumCubes(a: Int, b: Int): Int = {
  var s = 0
  for (i <- a to b)
    s += cube(i)
  s
}

Notice that sumInt and sumCubes are nearly identical—they only differ in the expression that is added to s in every iteration of the loop.

These two functions are special cases of computing the expression

for different choices of the function \(f\).

If mathematics has a notation for this kind of common expression, then so should computer science. We should be able to write a function sum that takes the function \(f\) as a parameter.

In Scala, we can do this as follows:

def sum(f: Int => Int, a: Int, b: Int): Int = {
  var s = 0
  for (i <- a to b)
    s += f(i)
  s
}

We can now compute any special case easily:

scala> def id(x: Int) = x
id: (x: Int)Int
scala> def cube(x: Int) = x * x * x
cube: (x: Int)Int
scala> def sumInt(a: Int, b: Int) = sum(id, a, b)
sumInt: (a: Int, b: Int)Int
scala> def sumCubes(a: Int, b: Int) = sum(cube, a, b)
sumCubes: (a: Int, b: Int)Int
scala> sumInt(1, 10)
res5: Int = 55
scala> sumCubes(1, 10)
res6: Int = 3025

The type of the parameter f of the function sum is Int => Int. This type indicates a function that takes an argument of type Int and returns a result of type Int. In general, A => B is the type of a function takes an argument of type A and returns a result of type B.

Using functions as arguments allows us to avoid defining many similar functions—however, we still needed to define the mini-functions id and cube. Sometimes, it is tedious to define these small functions and to give them a name. The mini-function may not be used anywhere else in the program.

It should be possible to define a function without giving it a name. For other basic objects, we do this all the time: We do not need to name every string or every integer. For instance, we don't have to write this:

scala> def str: String = "Hello CS109"
scala> def a: Int = 13
scala> println(str); println(a)

Instead, we simply write:

println("Hello CS109"); println(13)

The value of an object written in the program is called a literal. For instance, writing 1234 is an integer literal, writing "CS109" is a string literal.

Modern programming languages like Scala allow us to write function literals as well: We can write a function without having to give it a name using the def keyword. A function literal is sometimes also called an anonymous function.

For example, the function that raises an integer to its cube is written as

(x: Int) => x * x * x

Here, (x: Int) is the parameter of the function, and x * x * x is its body.

An anonymous function with several parameters looks like this:

(x: Int, y: Int) => x + y

The effect of executing a function literal is to create a function object (without giving it a name).

A function object exists on the heap, like every other object. We can assign a name to it, or store a reference to it in an array or another object. And, since it is a function object, we can call it like a function.

Here we create a function object and immediately call it with an argument:

scala> ((x: Int) => x + 1)(3)
res7: Int = 4

Here we assign a name to the function object and use that to call it with different arguments:

scala> val f = (x: Int) => x + 1
f: Int => Int = <function1>
scala> f(7)
res8: Int = 8
scala> f(13)
res9: Int = 14

And here we store several function objects in an array:

scala> val g = Array((x: Int) => x * x,
     |               (x: Int) => x * x * x,
     |               (x: Int) => x * x * x * x)
g: Array[Int => Int] = Array(<function1>, <function1>, <function1>)

scala> (g(0)(2), g(1)(2), g(2)(2))
res10: (Int, Int, Int) = (4,8,16)

Coming back to our summation functions from the beginning, we can now write them like this:

def sumInt(a: Int, b: Int): Int = sum((x: Int) => x, a, b)
def sumCubes(a: Int, b: Int): Int = sum((x : Int) => x * x * x, a, b)

In fact, in this case the compiler can determine the type of the arguments in the function literal automatically. The compiler knows that the first argument of sum is a function of type Int => Int, and so it knows that the type of any function literal written as an argument should be of this type. Therefore we can omit the type in the function literal:

def sumInt(a: Int, b: Int): Int = sum(x => x, a, b)
def sumCubes(a: Int, b: Int): Int = sum(x => x * x * x, a, b)

Functions like sum are called higher-order functions because they take another function object as an argument: A higher-order function is a "meta-function" that works on other functions.

Higher-order functions allow us to naturally express ideas where a function is part of the input to a problem, such as:

• print a table of function values for a given function
• integrating a function numerically
• finding a fixed point of a function.

You can read more about function objects in the Scala documentation.