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

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

  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?
/* 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)