Exercise 1.1: Write a function sum that, given two integer bounds and and a function , computes a summation.


$$ sum ~ n ~ m ~ f = \sum_{i=n}^{m} f(i) $$
def sum(n: Int, m: Int, f: Int => Int): Int = 
  if (n > m) 0
  else f(n) + sum(n +1, m, f)

def sumTailRecursive(n: Int, m: Int, f: Int => Int) = {
  def iter(i: Int, acc: Int): Int = 
    if (i > m) acc
    else iter (i + 1, f(i + acc))
  iter(n, 0)
}

println("Sum not tail recursive: " + sum(1, 10, x => x))
println("Sum tail recursive: " + sumTailRecursive(1, 10, x => x))

 

Exercise 1.2: Euclid’s algorithm computes the greatest common divisor (GCD) of two integers. It is one of the oldest known algorithms, appearing in Euclid’s Elements in roughly 300 BC. It can be defined in pseudo-code as follows, where < - represents assignment.

gcd(n, m) = 
  while m = 0
     if n > m
       n < - n - m
     else
       m <- m - n
   return n

Write an Scala function %% that computes the GCD using Euclid’s algorithm (so n %% m is the GCD of the integers n and m). You should define it without assignment, as recursive function. [Note, this is Euclid’s original definition of the algorithm. More modern versions usually use a modulus operation instead of subtraction.

class IntWithGCD(n: Int) {
  val value = n
  def %% (that: IntWithGCD): IntWithGCD =
    if (that == 0) this
    else if (this > that) (this - that) %% that
    else this %% (that - this)

  def < (that: IntWithGCD) = 
    this.value < that.value

  def > (that: IntWithGCD) =
    that < this

  def == (that: IntWithGCD) =
    that.value == this.value

  def == (that: Int) =
    that == this.value

  def - (that: IntWithGCD) = 
    new IntWithGCD(this.value - that.value)

  override def toString = this.value.toString
}

implicit def intToIntWithGCD(x: Int) = new IntWithGCD(x)

println("GCD 4 and 8: " + 8 %% 4)

 

Exercise 1.3: Suppose you have a function on integers that is monotonically increasing over some range of arguments from up to . That is, . Write a function search that finds the smallest argument where .

// A simple O(n) tail-recursive implementation
def search (n: Int) (f: Int => Int): Int = {
  def iter(i: Int): Int = 
    if (f(i) >= 0) i
    else iter(i+1)
  iter(0)
}

// A faster O(log(n)) tail-recursive implementation
def search2 (n: Int) (f: Int => Int): Int = {
  def iter(i: Int, acc: Int): Int =
    if (i < acc - 1) {
      val k = (i + acc) / 2
      if (f(k) >= 0) iter(i, k)
      else iter(k, acc)
    } else
      acc
  iter(0, n)
}

println("Search O(n): " + search (10) (x => x - 1))
println("Search Log(n): " + search2 (10) (x => x - 1))

 

Exercise 1.4: A dictionary is a data structure that represents a map from keys to values. A dictionary has three operations:

  • empty : dictionary
  • add : dictionary -> key -> value -> dictionary
  • find : dictionary -> key -> value

The value empty is an empty dictionary; the expression add dict key value takes an existing dictionary dict and augments it with a new binding and the expression find dict key fetches the value in the dictionary dict associated with the key.

One way to implement a dictionary is to represent it as a function from keys to values. Let’s assume we are building a dictionary where the key type is string, the value type is int, and the empty dictionary maps every key to zero. This dictionary can be implemented abstractly as follows, where we write for the map from keys to values.

empty = key -> 0
add(dict, key, v) = key' -> if (key' = key) v else dict(key)
find(dict, key) = dict(key)

1. Implement the dictionary in Scala.

2. Suppose we have constructed several dictionaries as follows.

let dict1 = add empty "x" 1
let dict2 = add dict1 "y" 2
let dict3 = add dict2 "x" 3
let dict4 = add dict3 "y" 4

What are the values associated with “x” and “y” in each of the four dictionaries?

// 1 Implement the dictionary in Scala.
def empty = (key: String) => 0
def add(dict: String => Int, key: String, v: Int) = 
  (keyl: String) => if (keyl == key) v else dict(key)
def find(dict: String => Int, key: String) = dict(key)

// 2. What are the values associated with "x" and "y" in each of the four
// dictionaries?
val dict1 = add(empty, "x", 1)
val dict2 = add(dict1, "y", 2)
val dict3 = add(dict2, "x", 3)
val dict4 = add(dict3, "y", 4)

println("dict1['x'] = " + dict1("x"))
println("dict2['x'] = " + dict2("x"))
println("dict3['x'] = " + dict3("x"))
println("dict4['x'] = " + dict4("x"))
println("dict1['y'] = " + dict1("y"))
println("dict2['y'] = " + dict2("y"))
println("dict3['y'] = " + dict3("y"))
println("dict4['y'] = " + dict4("y"))

 

Exercise 1.5: Partial application is sometimes used to improve the performance of a multi-argument function when the function is to be called repeatedly with one or more of its arguments fixed. Consider a function that is to be called multiple times with fixed. First, the function must be written in a form from some functions and , where represents the part of the computation that uses only the value . We then write it in OCaml as follows.

let f x =
      let z = g(x) in
        fun y -> h(z, y)

Calling f on its first argument computes and returns a function that uses the value (without re-computing it).

Consider one root of a quadratic equation specified by the by the quadratic formula . Suppose we wish to to evaluate the quadratic formula for multiple values of with and fixed. Write a function to compute the formula efficiently.

def r(b: Double, c: Double): (Double => (Double, Double)) = {
  val bMinus = -b
  val bTimesb = b * b
  val fourC = 4.0 * c
  (a: Double) => ((bMinus + math.sqrt(bTimesb - fourC * a)) / (2.0 * a),
                  (bMinus - math.sqrt(bTimesb - fourC * a)) / (2.0 * a))
}

def baskara = r(5.0, 1.0)
val x = baskara(2.0)

println("Solution of 2x^2 + 5x + 1 = 0 is " + x)