# Notes of Scala course on Coursera -- Week 2 (1)

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

gcd(14, 21) is evaluated as follows:

Another example:

factorial(4) is evaluated as follows:

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

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.

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

Take the sum of the cubes of all the integers between a and b :

Take the sum of the factorials of all the integers between a and b :

All above are special cases of

$\sum_{n=a}^{b}f(n)$

for different values of f.

Can we factor out the common pattern?

### 2.2 Summing with Higher-Order Functions

Let’s define:

We can then write:

where

We can then write:

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

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:

#### Anonymous Functions are Syntactic Sugar

An anonymous function (x1 : T1, ..., xn : Tn) => E can always be expressed using def as follows:

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:

#### Exercise

The sum function uses linear recursion. Write a tail-recursion version by replacing the ???s

## 3. Currying

### 3.1 Motivation

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

sum is now a function that returns another function.

The returned function sumF applies the given function parameter f and sums the results.

We can define:

### 3.4 Consecutive Stepwise Applications

Can we avoid these middlemen : sumInts , sumCubes , … ?

Of course we can:

• 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:

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

### 3.6 Expansion of Multiple Parameter Lists

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

where n > 1, is equivalent to

where g is a fresh identifier. Or for short:

By repeating the process n times

is shown to be equivalent to

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

What is the type of sum ?

1. Write a product function that calculates the product of the values of a function for the points on a given interval.
2. Write factorial in terms of product.
3. Can you write a more general function, which generalizes both sum and product?