Scala by Example — Chapter 05

/**
 * Exercise 5.2.1 1. The sum function uses a linear recursion. Can you write a
 * tail-recursive one by filling in the ??’s?
 *
 * def sum(f: Int => Int)(a: Int, b: Int): Int = {
 *   def iter(a: Int, result: Int): Int = {
 *     if (??) ??
 *     else iter(??, ??)
 *   }
 *   iter(??, ??)
 * }
 */

def sum(f: Int => Int)(a: Int, b: Int): Int = {
  def iter(a: Int, result: Int): Int = {
    if (a > b)
      result 
    else
      iter(a + 1, f(a) + result)
  }
  iter(a, 0)
}

println(sum(x => x)(1, 30))
println(sum(x => x*x)(1, 30))

 

 

/**
 * Exercise 5.2.2 Write a function product that computes the product of the
 * values of functions at points over a given range.
 */

def product(f: BigInt => BigInt)(a: BigInt, b: BigInt): BigInt = {
  def iter(a: BigInt, result: BigInt): BigInt = {
    if (a > b)
      result 
    else
      iter(a + 1, f(a) * result)
  }
  iter(a, 1)
}

println(product(x => x)(1, 30))
println(product(x => x*x)(1, 30))

 

 

/**
 * Exercise 5.2.3 Write factorial in terms of product.
 */

def product(f: BigInt => BigInt)(a: BigInt, b: BigInt): BigInt = {
  def iter(a: BigInt, result: BigInt): BigInt = {
    if (a > b)
      result 
    else
      iter(a + 1, f(a) * result)
  }
  iter(a, 1)
}

def factorial(x: BigInt) = product(x => x)(1, x)

println(factorial(5))
println(factorial(10))
println(factorial(100))

 

 

/**
 * Exercise 5.2.4 Can you write an even more general function which
 * generalizes both sum and product?
 */

def general(op: (BigInt, BigInt) => BigInt)(f: BigInt => BigInt)
           (a: BigInt, b: BigInt): BigInt = {
  def iter(a: BigInt, result: BigInt): BigInt = {
    if (a > b)
      result 
    else
      iter(a + 1, op(f(a), result))
  }
  iter(a, 1)
}

def sum(f: BigInt => BigInt)(a: BigInt, b: BigInt): BigInt =
  general((x, y) => x + y)(f)(a, b)

def product(f: BigInt => BigInt)(a: BigInt, b: BigInt): BigInt =
  general((x, y) => x * y)(f)(a, b)


println(sum(x => x)(1, 30))
println(sum(x => x*x)(1, 30))

println(product(x => x)(1, 30))
println(product(x => x*x)(1, 30))

 

 

/**
 * Exercise 5.3.1 Write a function for cube roots using fixedPoint and
 * averageDamp.
 */

def abs(x: Double) = if (x >= 0) x else -x
val tolerance = 2.2250738585072014E-308 
def isCloseEnough(x: Double, y: Double) = abs((x - y) / 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)
}

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

def cube(x: Double) = fixedPoint(averageDamp(y => x/(y * y)))(1.0)


println(cube(8))
println(cube(27))
println(cube(64))
println(cube(125))