Higher Order Functions

Functional languages treat functions as first-class values, that is, like any other value. Higher order functions take other functions as parameters or return value.

Let's make three functions that sum up a range of integers, a range of their cubes, and a range of their factorials.

def sumInts(a: Int, b: Int): Int =
     if (a>b) 0 else a + sumInts(a+1, b)
def sumCubes(a: Int, b: Int): Int =
     if (a>b) 0 else cube(a) + sumCubes(a+1, b)
def sumFactorials(a: Int, b: Int): Int =
     if (a>b) 0 else fact(a) + sumFactorials(a+1, b)

You notice that these three functions are nearly identical, except for one area: what they do at each value of a. We want to factor out the common things. How can we do this? Higher order functions!

We can make three functions to do the work at each level. Say,

1. def id(x: Int):Int = x
2. def cube(x: Int):Int = x * x * x
3. def fact(x: Int):Int = if (x==0) 1 else x * fact(x-1)

We can define a single function that can do all the work:
def sum(f: Int => Int, a: Int, b: Int):Int =
     if (a>b) 0
     else f(a) + sum(f, a+1, b)

def sumInts(a: Int, b: Int) = sum(id, a, b)
def sumCubes(a: Int, b: Int) = sum(cube, a, b)
def sumFactorials(a: Int, b: Int) = sum(fact, a, b)

In sum, f is the type of function that maps Int to Int. As you can see, this makes the code a lot more compact and breaks it down into more modules. However, we had to define 3 auxilliary functions: id, cube, and fact. These can be hidden using anonymous functions.