1. Recursion and Tail Recursion
1.1 Examples of Recursion
gcd(14, 21) is evaluated as follows:
factorial(4) is evaluated as follows:
1.2 Tail Recursion
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.
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
for different values of f.
Can we factor out the common pattern?
2.2 Summing with Higher-Order Functions
We can then write:
We can then write:
2.3 Function Types
A => B is the type of a function takes an argument of type
A and returns a result of type
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
- 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:
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:
sum function uses linear recursion. Write a tail-recursion version by replacing the
b get passed unchanged from
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 :
sumCubes , … ?
Of course we can:
cubeand returns the sum of cubes function.
sum(cube)is therefore equivalent to
- This function is next applied to the arguments
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
n > 1, is equivalent to
g is a fresh identifier. Or for short:
By repeating the process n times
is shown to be equivalent to
3.7 More Function Types
What is the type of
Note that functional types associate to the right. That is to say that
is equivalent to
- Write a
productfunction that calculates the product of the values of a function for the points on a given interval.
- Write factorial in terms of
- Can you write a more general function, which generalizes both