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 tailcalls.
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 tailrecursive 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. HighOrder Functions
In functional languages, functions are firstclass 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
for different values of f.
Can we factor out the common pattern?
2.2 Summing with HigherOrder 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 tailrecursion version by replacing the ???
s


Answer:


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.
3.3 Stepwise Applications
We can define:


3.4 Consecutive Stepwise Applications
Can we avoid these middlemen : sumInts
, sumCubes
, … ?
Of course we can:


sum(cube)
appliessum
tocube
and returns the sum of cubes function.sum(cube)
is therefore equivalent tosumCubes
. 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 (19001982), 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
?
Answer:


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


is equivalent to


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
andproduct
?



