Scala By Example Chapter 9 Solutions - Exercise 9.2.1

Exercise 9.2.1 Design a tail-recursive version of length.

Ah, tail recursion again. Re-iterating that in a tail recursion, the last line of the function has to be a pure call to itself. To achieve this, an extra parameter needs to be passed to the function that keeps track of some relevant state.
We are getting good at this now, arent we?

	object TailRecursiveListLength {
	def trlength(l: List[Int], counter: Int): Int = l match {
	case Nil => counter
	case x :: xs => trlength(xs, counter + 1)
	}
	def main(args: Array[String]) {
	println("Length of list () is: " + trlength(List(), 0))
	println("Length of list (1,6,2,5,8,93) is: " + trlength(List(1,6,2,5,8,93), 0))
	}
	}

view raw TailRecursiveListLength.scala hosted with ❤ by GitHub

Scala By Example Chapter 9 Solutions - Exercise 9.1.1

Exercise 9.1.1 Provide an implementation of the missing function insert.

Insert will also be recursive, and its pretty easy to lay down the flow. Do not forget to concatenate the head after insert is applied on reduced versions of the list since we will need to return the whole inserted list and not a subset.

	object ListSort {
	def isort(xs: List[Int]): List[Int] =
	if (xs.isEmpty) Nil
	else insert(xs.head, isort(xs.tail))
	def insert(head: Int, xs: List[Int]): List[Int] =
	if (xs.isEmpty) List(head)
	else if (head > xs.head) xs.head :: insert(head, xs.tail)
	else head :: xs
	def main(args: Array[String]) {
	val l = List(6,4,8,12,1,7,22,10)
	println("List is: " + l)
	println("Sorted List is: " + isort(l))
	}
	}

view raw ListSort.scala hosted with ❤ by GitHub

Scala By Example Chapter 7 Solutions - Exercise 7.2.2

Exercise 7.2.2 Complete the following implementations of function contains and insert for IntTree’s.

This is similar to the IntSet implementations in Chapter 6.

	object IntTreeTest {
	abstract class IntTree
	case object EmptyTree extends IntTree
	case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree
	def contains(t: IntTree, v: Int): Boolean = t match {
	case EmptyTree => false
	case Node(e, l, r) =>
	if (v < e) contains(l, v)
	else if (v > e) contains(r, v)
	else true
	}
	def insert(t: IntTree, v: Int): IntTree = t match {
	case EmptyTree => Node(v, EmptyTree, EmptyTree)
	case Node(e, l, r) =>
	if (v < e) Node(e, insert(l, v), r)
	else if (v > e) Node(e, l, insert(r, v))
	else t
	}
	def main(args: Array[String]) {
	val t = insert(insert(insert(insert(insert(EmptyTree, 11), 1), 20), 18), 25)
	println("Tree is: " + t)
	println("Does Tree contain 20?: " + (if (contains(t, 20)) "Yes" else "No"))
	println("Does Tree contain 15?: " + (if (contains(t, 15)) "Yes" else "No"))
	}
	}

view raw IntTreeTest.scala hosted with ❤ by GitHub

Scala By Example Chapter 6 Solutions - Exercise 6.0.3

Exercise 6.0.3 Write an implementation Integer of integer numbers The implementation should support all operations of class Nat while adding two methods def isPositive: Boolean def negate: Integer

This will be revisited later.

Scala By Example Chapter 6 Solutions - Exercise 6.0.2

Exercise 6.0.2 Add a method def excl(x: Int) to return the given set without the element x. To accomplish this, it is useful to also implement a test method def isEmpty: Boolean for sets.

This will be revisited later.

Scala By Example Chapter 6 Solutions - Exercise 6.0.1

Exercise 6.0.1 Write methods union and intersection to form the union and intersection between two sets.

This will be revisited later.

Scala By Example Chapter 5 Solutions - Exercise 5.3.1

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

Both fixedPoint and averageDamp functions remain the same. Instead of sqrt, now theres a cbrt function which calculates the cube root. The math library is used to avail of the exponential function.

	object FixedPoint {
	var tolerance = 0.0001
	def abs(x: Double) = if (x >= 0) x else -x
	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)
	println(next)
	if (isCloseEnough(guess, next)) next
	else iterate(next)
	}
	iterate(firstGuess)
	}
	def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2
	def cbrt(x: Double) = fixedPoint(averageDamp(y => x/math.pow(y,2)))(1.0)
	def main(args: Array[String]) {
	println("calculating cube root of 2 : " + cbrt(2))
	println("calculating cube root of 8 : " + cbrt(8))
	}
	}

view raw cuberoot.scala hosted with ❤ by GitHub

Scala By Example Chapter 5 Solutions - Exercise 5.2.4

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

This function abstracts out the operation which can be passed in as a sum or product function. One thing to be noted here is that an extra argument needs to be passed as the base case which would be 0 for a sum and 1 for a product.

	object OperatorOverRange {
	def operateOverRange(f: Int => Int)(operate: (Int, Int) => Int)(base: Int)(a: Int, b:Int): Int =
	if (a > b) base else operate(f(a), operateOverRange(f)(operate)(base)(a + 1, b))
	def main(args: Array[String]) {
	println("Sum of range of numbers from 3 to 8 is: " + operateOverRange(x => x)((x,y) => x + y)(0)(3,8))
	println("Product of range of numbers from 3 to 8 is: " + operateOverRange(x => x)((x,y) => x * y)(1)(3,8))
	}
	}

view raw OperatorOverRange.scala hosted with ❤ by GitHub

Scala By Example Chapter 5 Solutions - Exercise 5.2.3

Exercise 5.2.3 Write factorial in terms of product.

	object Factorial {
	def product(f: Int => Int)(a: Int, b:Int): Int = {
	if (a > b) 1 else f(a) * product(f)(a + 1, b)
	}
	def factorial(n: Int): Int = {
	product(x => x)(1, n)
	}
	def main(args: Array[String]) {
	println("Factorial of 6 is: " + factorial(6))
	}
	}

view raw factorial2.scala hosted with ❤ by GitHub

Scala By Example Chapter 5 Solutions - Exercise 5.2.2

Exercise5.2.2 Write a function product that computes the product of the values of functions at points over a given range.

This is very similar to the sum function that is already worked out in the chapter.

	object HigherOrderFunctions {
	def product(f: Int => Int)(a: Int, b:Int): Int = {
	if (a > b) 1 else f(a) * product(f)(a + 1, b)
	}
	def main(args: Array[String]) {
	println("Product of range of numbers from 3 to 8 is: " + product(x => x)(3,8))
	}
	}

view raw higherorderfunctions.scala hosted with ❤ by GitHub

Scala By Example Chapter 5 Solutions - Exercise 5.2.1

Exercise 5.2.1 1. The sum function uses a linear recursion. Can you write a tail- recursive one by filling in the ??’s?

The key is to understand that converting linear recursion to a tail-recursive version involves carrying over a computed value over to the next iteration. Also, note that the call to the iter function at the end need not take in a and b as parameters directly but can be computed values. Thats what facilitates the tail-recursive version. Here's my solution to the exercise.

	object FirstClassFunctions {
	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)
	}
	def main(args: Array[String]) {
	println("Sum is: " + sum(x => x)(1,10))
	}
	}

view raw tailrecursivesum.scala hosted with ❤ by GitHub

Scala by Example Chapter 4 Solutions Exercise 4.6.1

Exercise 4.6.1 Design a tail-recursive version of factorial

A tail-recursive call is a method where the last step of the method is to call itself. The key point to remember is that the call should be a pure call and not an expression that involves a call to the method. If it is a pure call, the stack frame can be reused rather than allocating a new stack frame. The version of the factorial function seen in most places is a recursive one but its not tail-recursive since the last line of the factorial function usually calls n * factorial(n -1).

Here's the tail-recursive version of factorial. As you can see below, making a tail-recursive version involves adding an extra parameter. This parameter involves a computation that's different from just a reduction as in simple recursion.

	object TailRecursiveFactorial {
	def factorial(n: Int, product: Int): Int =
	if (n == 1) product else factorial(n - 1, n * product)
	def main(args: Array[String]) {
	println("Factorial of 8 is: " + factorial(8,1))
	}
	}

view raw tailrecursivefactorial.scala hosted with ❤ by GitHub