Functional Loops

Conditional Expressions

To express choosing between two alternatives, Scala has a conditional expression if-else.

It looks like a if-else in Java, but is used for expressions, not statements.

Example:

def abs(x: Double) = if (x >= 0) x else -x

x >= 0 is a predicate, of type Boolean.

Boolean Expressions

Boolean expressions b can be composed of

true  false      // Constants
!b               // Negation
b && b           // Conjunction
b || b           // Disjunction

and of the usual comparison operations:

e <= e, e >= e, e < e, e > e, e == e, e != e

Rewrite rules for Booleans

Here are reduction rules for Boolean expressions (e is an arbitrary expression):

!true --> false
!false --> true
true && e --> e
false && e --> false
true || e --> true
false || e --> e

Note that && and || do not always need their right operand to be evaluated.

We say these expressions use “short-circuit evaluation”.

Computing the Square Root of a Value

We will define in this section a method

/** Calculates the square root of parameter x */
def sqrt(x: Double): Double = ...

The classical way to achieve this is by successive approximations using Newton's method.

Method

To compute sqrt(x):

  • Start with an initial estimate y (let's pick y = 1).
  • Repeatedly improve the estimate by taking the mean of y and x/y.

Example: Evaluation of the square root of 2 (x = 2):

Estimation          Quotient              Mean
1                   2 / 1 = 2             1.5
1.5                 2 / 1.5 = 1.333       1.4167
1.4167              2 / 1.4167 = 1.4118   1.4142
1.4142              ...                   ...

Implementation in Scala

First, we define a method which computes one iteration step:

def sqrtIter(guess: Double, x: Double): Double =
  if (isGoodEnough(guess, x)) guess
  else sqrtIter(improve(guess, x), x)

Note that sqrtIter is recursive, its right-hand side calls itself.

Recursive methods need an explicit return type in Scala.

For non-recursive methods, the return type is optional.

Second, we define a method improve to improve an estimate and a test to check for termination:

def improve(guess: Double, x: Double) =
  (guess + x / guess) / 2

def isGoodEnough(guess: Double, x: Double) =
  abs(guess * guess - x) < 0.001

Third, we define the sqrt function:

def sqrt(x: Double) = sqrtIter(1.0, x)

Summary

You have seen simple elements of functional programing in Scala.

  • arithmetic and boolean expressions
  • conditional expressions if-else
  • functions with recursion

You have learned the difference between the call-by-name and call-by-value evaluation strategies.

You have learned a way to reason about program execution: reduce expressions using the substitution model.

Exercise

Complete the following method definition that computes the factorial of a number: 

def factorial(n: Int): Int =
  if (n == res0) res1
  else factorial(n - 1) * n

factorial(3) shouldBe 6
factorial(4) shouldBe 24