Notes of Scala course on Coursera  Week 2 (2)
Here are my notes for the week 2’s lecture of Functional Programming Principles in Scala on Coursera.
4. Example: Finding Fixed Points
4.1 Finding a fixed point of a function
A number x is called a fixed point of a function f if
For some functions f we can locate the fixed points by starting with an initial estimate and then by applying f in a repetitive way.
until the value does not vary anymore (or the change is sufficiently small).
4.2 Programmatic Solution
This leads to the following function for finding a fixed point:


4.3 Return to Square Roots
Here is a specification of the sqrt function:sqrt(x) = the number y such that y * y = x
Or, by dividing both sides of the equation with y :sqrt(x) = the number y such that y = x / y
Consequently, sqrt(x)
is a fixed point of the function (y => x / y)
.
4.3.1 First Attempt of sqrt using fixedPoint


Unfortunately, this does not converge.
Let’s add a println
instruction to the function fixedPoint
so we can follow the current value of guess
:


sqrt(2)
then produces:


4.3.2 Average Damping
One way to control such oscillations is to prevent the estimation from varying too much. This is done by averaging successive values of the original sequence:


This produces


In fact, if we expand the fixed point function fixedPoint
we find a similar square root function to what we developed last week.
4.4 Functions as Return Values
The previous examples have shown that the expressive power of a language is greatly increased if we can pass function arguments.
The following example shows that functions that return functions can also be very useful.
Consider again iteration towards a fixed point.
We begin by observing that sqrt(x)
is a fixed point of the function y => x / y
.
Then, the iteration converges by averaging successive values.
This technique of stabilizing by averaging is general enough to merit being abstracted into its own function.


Exercise:
Write a square root function using fixedPoint and averageDamp.
Answer:


This expresses the elements of the algorithm as clearly as possible.
4.5 Summary
We saw last week that the functions are essential abstractions because they allow us to introduce general methods to perform computations as explicit and named elements in our programming language.
This week, we’ve seen that these abstractions can be combined with higherorder functions to create new abstractions. As a programmer, one must look for opportunities to abstract and reuse.
The highest level of abstraction is not always the best, but it is important to know the techniques of abstraction, so as to use them when appropriate.
5. Scala Syntax Summary
5.1 Types
A type can be:
 A numeric type:
Int
,Double
(andByte
,Short
,Char
,Long
,Float
),  The Boolean type with the values
true
andfalse
,  The String type,
 A function type, like
Int => Int
,(Int, Int) => Int
.
Later we will see more forms of types.
5.2 Expressions
An expression can be:
 An identifier such as
x
,isGoodEnough
,  A literal, like
0
,1.0
,"abc"
,  A function application, like
sqrt(x)
,  An operator application, like
x
,y + x
,  A selection, like
math.abs
,  A conditional expression, like
if (x < 0) x else x
,  A block, like
{ val x = math.abs(y) ; x * 2 }
 An anonymous function, like
x => x + 1
.
5.3 Definitions
A definition can be:
 A function definition, like
def square(x: Int) = x * x
 A value definition, like
val y = square(2)
A parameter can be:
 A callbyvalue parameter, like
(x: Int)
,  A callbyname parameter, like
(y: => Double)