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:

```
val tolerance = 0.0001
def isCloseEnough(x: Double, y: Double) =
abs((x - y) / x) / x < tolerance
def fixedPoint(f: Double => Double)(firstGuess: Double) = {
def iterate(guess: Double): Double = {
val next = f(guess)
if (isCloseEnough(guess, next)) next
else iterate(next)
}
iterate(firstGuess)
}
```

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

```
def sqrt(x: Double) =
fixedPoint(y => x / y)(1.0)
```

Unfortunately, this **does not converge**.

Let’s add a `println`

instruction to the function `fixedPoint`

so we can follow the current value of `guess`

:

```
def fixedPoint(f: Double => Double)(firstGuess: Double) = {
def iterate(guess: Double): Double = {
val next = f(guess)
println(next) // print out the value
if (isCloseEnough(guess, next)) next
else iterate(next)
}
iterate(firstGuess)
}
```

`sqrt(2)`

then produces:

```
2.0
1.0
2.0
1.0
```

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

`def sqrt(x: Double) = fixedPoint(y => (y + x / y) / 2)(1.0)`

This produces

```
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
1.4142135623746899
```

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.

`def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2`

#### Exercise:

Write a square root function using fixedPoint and averageDamp.

**Answer:**

`def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)`

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 higher-order 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`

(and`Byte`

,`Short`

,`Char`

,`Long`

,`Float`

), - The
*Boolean*type with the values`true`

and`false`

, - 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
*call-by-value*parameter, like`(x: Int)`

, - A
*call-by-name*parameter, like`(y: => Double)`