Here are my notes for the week 2’s lecture of Functional Programming Principles in Scala on Coursera.

## 1. Recursion and Tail Recursion

### 1.1 Examples of Recursion

```
/* Euclid's Algorithm */
def gcd(a: Int, b: Int): Int =
if (b == 0) a else gcd(b, a % b)
```

`gcd(14, 21)`

is evaluated as follows:

```
gcd(14, 21)
--> if (21 == 0) 14 else gcd(21, 14 % 21)
--> if (false) 14 else gcd(21, 14 % 21)
--> gcd(21, 14 % 21)
--> gcd(21, 14)
--> if (14 == 0) 21 else gcd(14, 21 % 14)
-->> gcd(14, 7)
-->> gcd(7, 0)
--> if (0 == 0) 7 else gcd(0, 7 % 0)
--> 7
```

Another example:

```
def factorial(n: Int): Int =
if (n == 0) 1 else n * factorial(n - 1)
```

`factorial(4)`

is evaluated as follows:

```
factorial(4)
--> if (4 == 0) 1 else 4 * factorial(4 - 1)
-->> 4 * factorial(3)
-->> 4 * (3 * factorial(2))
-->> 4 * (3 * (2 * factorial(1)))
-->> 4 * (3 * (2 * (1 * factorial(0))))
-->> 4 * (3 * (2 * (1 * 1)))
```

### 1.2 Tail Recursion

**Implementation Consideration:**

If a function calls itself **as its last action**, the function’s **stack frame** can be **reused**. This is called *tail recursion*.

Tail recursive functions are iterative processes.

In general, if the last action of a function consists of calling a function (which may be the same), one stack frame would be sufficient for both functions. Such calls are called **tail-calls**.

### 1.3 Tail Recursion in Scala

In Scala, only directly recursive calls to the current function are optimized.

One can require that a function is tail-recursive using a @tailrec annotation:

```
@tailrec
def gcd(a: Int, b: Int): Int = ...
```

If the annotation is given, and the implementation of gcd were not tail recursive, an **error** would be issued.

#### Exercise: Tail recursion

Design a tail recursive version of factorial.

```
def factorial(n: Int): Int = {
def loop(acc: Int, n: Int): Int =
if (n == 0) acc else loop(acc * n, n - 1)
loop(1, n)
}
```

## 2. High-Order Functions

In functional languages, functions are *first-class values*.

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.**

### 2.1 Begin with an Example:

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 fact(a) + sumFactorials(a + 1, b)
```

All above are special cases of

for different values of f.

Can we factor out **the common pattern**?

### 2.2 Summing with Higher-Order Functions

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 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)
```

where

We can then write:

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

### 2.3 Function Types

The type `A => B`

is the type of a *function* 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.

### 2.4 Anonymous Functions

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`

. - We would like function literals, which let us write a function without giving it a name.
- These are called
*anonymous functions*.

#### Example: 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`

#### Anonymous Functions are Syntactic Sugar

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)
```

#### Exercise

The `sum`

function uses linear recursion. Write a tail-recursion version by replacing the `???`

s

```
def sum(f: Int => Int)(a: Int, b: Int): Int = {
def loop(a: Int, acc: Int): Int =
if (???) ???
else loop(???, ???)
loop(???, ???)
}
```

**Answer:**

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

## 3. Currying

### 3.1 Motivation

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

#### Question

Note that `a`

and `b`

get passed unchanged from `sumInts`

and `sumCubes`

into `sum`

.

Can we be even shorter by **getting rid of these parameters**?

### 3.2 Functions Returning Functions

Let’s rewrite sum as follows.

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

`sum`

is now a function that **returns another function**.

The returned function `sumF`

applies the given function parameter `f`

and sums the results.

### 3.3 Stepwise Applications

We can define:

```
def sumInts = sum(x => x)
def sumCubes = sum(x => x * x * x)
def sumFactorials = sum(fact)
```

### 3.4 Consecutive Stepwise Applications

Can we avoid these *middlemen* : `sumInts`

, `sumCubes`

, … ?

Of course we can:

`sum(cube)(1, 10)`

`sum(cube)`

applies`sum`

to`cube`

and returns the sum of cubes function.`sum(cube)`

is therefore equivalent to`sumCubes`

.- This function is next applied to the arguments
`(1, 10)`

.

Generally, function application **associates to the left**:

`sum(cube)(1, 10) == (sum(cube))(1, 10)`

### 3.5 Multiple Parameter Lists

The definition of *functions that return functions* is so useful in functional programming that there is a *special syntax* for it in Scala.

For example, the following definition of `sum`

is equivalent to the one with the nested `sumF`

function, but shorter:

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

### 3.6 Expansion of Multiple Parameter Lists

In general, a definition of a function with multiple parameter lists

`def f(args_1)...(args_n) = E`

where `n > 1`

, is equivalent to

`def f(args_1)...(args_[n-1]) = {def g(args_n) = E; g}`

where `g`

is a fresh identifier. Or for short:

`def f(args_1)...(args_[n-1]) = (args_n => E)`

By repeating the process *n* times

`def f(args_1)...(args_n) = E`

is shown to be equivalent to

`def f = (args_1 => (args_2 => ...(args_n => E)...))`

This style of definition and function application is called currying, named for its instigator, Haskell Brooks Curry (1900-1982), a twentieth century logician.

In fact, the idea goes back even further to Sch?nfinkel and Frege, but the term “currying” has stuck.

### 3.7 More Function Types

Question: Given

`def sum(f: Int => Int)(a: Int, b: Int): Int = ...`

What is the type of `sum`

?

**Answer:**

`(Int => Int) => (Int, Int) => Int`

Note that functional types **associate to the right**. That is to say that

`Int => Int => Int`

is equivalent to

`Int => (Int => Int)`

#### Exercise

- Write a
`product`

function that calculates the product of the values of a function for the points on a given interval. - Write factorial in terms of
`product`

. - Can you write a more general function, which generalizes both
`sum`

and`product`

?

```
/* Ex1 & Ex2*/
def product(f: Int => Int)(a: Int, b: Int): Int =
if (a > b) 1
else f(a) * product(f)(a + 1, b)
product(x => x * x)(3, 4) // squares product, (3 * 3) * (4 * 4)
def fact(n: Int) = product(x => x)(1, n)
fact(5) // product(x => x)(1, 5)
```

```
/* Ex3 */
def mapReduce(f: Int => Int, combine: (Int, Int) => Int, zero: Int): Int =
if (a > b) zero
else combine(f(a), mapReduce(f, combine, zero)(a + 1, b))
def product(f: Int => Int)(a: Int, b: Int): Int = mapReduce(f, (x, y) => x * y, 1)(a, b)
product(x => x * x)(3, 4) // mapReduce(x => x * x, (x, y) => x * y, 1)(3, 4)
```