Functional languages treat functions as *first-class values*.

This means that, like any other value, a function can be passed as a parameter and returned as a result.

This provides a flexible way to compose programs.

Functions that take other functions as parameters or that return functions
as results are called *higher order functions*.

Consider the following programs.

Take the sum of the integers between `a`

and `b`

:

```
def sumInts(a: Int, b: Int): Int =
if (a > b) 0 else a + sumInts(a + 1, b)
```

Take the sum of the cubes of all the integers between `a`

and `b`

:

```
def cube(x: Int): Int = x * x * x
def sumCubes(a: Int, b: Int): Int =
if (a > b) 0 else cube(a) + sumCubes(a + 1, b)
```

Take the sum of the factorials of all the integers between `a`

and `b`

:

```
def sumFactorials(a: Int, b: Int): Int =
if (a > b) 0 else factorial(a) + sumFactorials(a + 1, b)
```

Note how similar these methods are. Can we factor out the common pattern?

Let's define:

```
def sum(f: Int => Int, a: Int, b: Int): Int =
if (a > b) 0
else f(a) + sum(f, a + 1, b)
```

We can then write:

```
def id(x: Int): Int = x
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(factorial, a, b)
```

The type `A => B`

is the type of a *function* that
takes an argument of type `A`

and returns a result of
type `B`

.

So, `Int => Int`

is the type of functions that map integers to integers.

Similarly, `(A1, A2) => B`

is the type of functions that take two arguments
(of types `A1`

and `A2`

, respectively) and return a result of type `B`

.

More generally, `(A1, ..., An) => B`

is the type of functions that take `n`

arguments (of types `A1`

to An`) and return a result of type `

B`.`

Passing functions as parameters leads to the creation of many small functions.

Sometimes it is tedious to have to define (and name) these functions using `def`

.

Compare to strings: We do not need to define a string using `val`

. Instead of:

`val str = "abc"; println(str)`

We can directly write:

`println("abc")`

because strings exist as *literals*. Analogously we would like function
literals, which let us write a function without giving it a name.

These are called *anonymous functions*.

Example of a function that raises its argument to a cube:

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

Here, `(x: Int)`

is the *parameter* of the function, and
`x * x * x`

is its *body*.

The type of the parameter can be omitted if it can be inferred by the compiler from the context.

If there are several parameters, they are separated by commas:

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

An anonymous function `(x1: T1, …, xn: Tn) => e`

can always be expressed using `def`

as follows:

`{ def f(x1: T1, …, xn: Tn) = e ; f }`

where `f`

is an arbitrary, fresh name (that's not yet used in the program).

One can therefore say that anonymous functions are *syntactic sugar*.

Using anonymous functions, we can write sums in a shorter way:

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

The `sum`

function uses linear recursion. Complete the following tail-recursive
version:

```
def sum(f: Int => Int, a: Int, b: Int): Int = {
def loop(x: Int, acc: Int): Int =
if (x > b) acc
else loop(x + 1, acc + f(x))
loop(a, res0)
}
sum(x => x, 1, res1) shouldBe 55
```