metagear.de
Solutions to the Exercises in the "Scala By Example" Manual

May 30, 2011 · Robert Söding

Updated, October 29, 2012
The update affects exercise 9.4.1 a.
Updated, November 16, 2011
The updates affect exercises 6.0.3 and – remarkably – 16.0.1.

Preface

These are solutions for the exercises in Martin Odersky's Scala By Example manual.
To my knowledge, official, or commonly approved, solutions do not exist. Moreover, only sporadically have single, or few, solutions been published by third-party authors. The only (well, half-way) comprehensive collection I'm aware of is the one provided by whiter4bbit. – In contrast, this article covers any and every exercise.
Exercise 16.0.1, which is exceptionally hard, has been worked on by Nada Amin.
Most code samples in the article at hand are shortened for clarity. You can download the entire source code, where every solution has a startable main method and is usually accompanied by corresponding unit tests.
Any feedback is appreciated and may be directed to . Should you solve any of these exercises yourself and find your solutions more accurate or of another approach than mine, I'd be grateful if you could send yours over.
Cheers
P.S.: Suspecting whether posting the solutions might be regarded a spoiler, I emailed Mr. Odersky about that concern. – Well, he meant that publishing the article sounded like a good idea! – Kind, and cool, thanks! – So here we go.

Exercises

Expressions and Simple Functions

Exercise 4.4.1 – Understanding and Handling Floating Point Inaccuracy

Assignment

Given the following code: 
def sqrtIter(guess: Double, x: Double): Double =
        if (isGoodEnough(guess, x)) guess
        else sqrtIter(improve(guess, x), x)

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

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

def sqrt(x: Double) = sqrtIter(1.0, x)
The isGoodEnough test is not very precise for small numbers and might lead to non-termination for very large ones (why?). Design a different version of isGoodEnough which does not have these problems.

Resolution

While the number of real numbers is infinite, the number of binary representable numbers is finite – and so is the the number of floating-point numbers that the computer uses.
Floating point numbers can represent most real numbers by approximation only because there is no exact binary representation. The "gap", or distance, between adjacent floating-point numbers is smaller for small numbers, and becomes larger as the numbers increase (the larger its so-called exponent becomes, actually). Thus, an absolute value (a distance of 0.001 in the above code snippet) cannot be used in general-purpose functions.
The solution is to use the scala.math.ulp(Double): Double method – ulp meaning, "units in the last place", representing "the positive distance between this floating-point value and the double value next larger in magnitude".
For further information see a corresponding Wikipedia article on Accuracy Problems with Floating Point Numbers, the article Floating Point Encoding (for understanding the distance between floating-point numbers), the java.lang.Math ApiDoc [1] [2], and a Scala-User mailing list thread, on which this exercise gets discussed.
object Exercise_04_4_1 {
  def sqrtIter(guess: Double, x: Double): Double =
    if (isGoodEnough(guess, x)) guess
    else sqrtIter(improve(guess, x), x)

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

  def isGoodEnough(guess: Double, x: Double) =
    abs(square(guess) - x) <= math.ulp(x)

  def square(x: Double) = x * x

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

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

  def main(args: Array[String]) {
    val x = sqrt(4)
    assert(x == 2)
  }
}

Exercise 4.4.2 – Newton’s Method of Successive Approximations

Assignment

Trace the execution of the sqrt(4) expression.

Resolution

Using the improve method, guess gets successively approximated to the root of the sqrt function:
1.0
2.5
2.05
2.000609756097561
2.0000000929222947
2.000000000000002
2.0
See the following articles for more information: The Newton-Raphson Method, Newton's method.

Exercise 4.6.1 – Understanding the Impact of, and Implementing, Tail Recursion

Assignment

Given the following function: 
def factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1)
Design a tail-recursive version of factorial.

Resolution

In contrast to other recursive functions, tail-recursive functions perform better – as subsequent, recursive, function calls can re-use the memory stack frame that has been reserved for the function. A function is tail-recursive when the call to itself is its very last operation.
See the StackOverflow thread Use of recursion in Scala when run in the JVM for a further discussion.
import annotation.tailrec

object Exercise_04_6_1 {
  val emptyProduct = 1

  def inefficientFactorial(n: Int): Int = {
    assert(n >= 0)

    if (n == 0) emptyProduct
    else n * inefficientFactorial(n - 1)
  }

  def factorial(n: Int): Int = {
    assert(n >= 0)

    @tailrec def factorial(n: Int, result: Int): Int =
      if (n == 0) result
      else factorial(n - 1, result * n)

    factorial(n, emptyProduct)
  }

  def main(args: Array[String]) {
    val result0 = factorial(5)
    val result1 = inefficientFactorial(5)

    assert(result0 == result1)
  }
}
The @tailrec annotation causes the compiler to throw an error if the annotated method cannot be compiled with tail-recursive optimizations (that is, re-structuring it to a loop).

First-Class Functions

Exercise 5.2.1 – Implementing Tail Recursion

Assignment

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(??, ??)
}

Resolution

import annotation.tailrec

object Exercise_05_2_1 extends Exercise_05_2_x {
  def linearSum(a: Int, b: Int): Int =
    if (a > b) 0
    else a + linearSum(a + 1, b)

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

  def main(args: Array[String]) {
    val result0 = sum(noOp)(2, 4)
    val result1 = linearSum(2, 4)

    assert(result0 == result1)
  }
}

Exercise 5.2.2 – Variation of Exercise 5.2.1: Implementing Tail Recursion

Assignment

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

Resolution

import annotation.tailrec

object Exercise_05_2_2 extends Exercise_05_2_x {
  def linearProduct(a: Int, b: Int): Int =
    if (a > b) 1
    else a * linearProduct(a + 1, b)

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

  def main(args: Array[String]) {
    assert(product(noOp)(2, 4) == linearProduct(2, 4))
    assert(product(noOp)(3, 6) == linearProduct(3, 6))
  }
}

Exercise 5.2.3 – Understanding the Factorial Function in the Context of Functional Programming

Assignment

Write factorial in terms of product.

Resolution

In my understanding, "in terms of product" means, computing "the product of the values of functions at points over a given range" (see exercise 5.2.2). For a factorial, that range is half-fixed – its left bound is its argument, and its right bound is 1. Beyond that difference, the product and factorial equally compute the product of each integer within that range.
There is no solution because of contradictory task criteria; nevertheless, we can observe that product equals a factorial except there are two variable (non-fixed) bounds, not one.

Exercise 5.2.4 – Implementing Higher-Order Functions

Assignment

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

Resolution

We're introducing a function parameter that takes a function itself:
def operate(f: Int => Int)
  (oper: (Int, Int) => Int)
  (a: Int, b: Int, init: Int): Int = {
  @tailrec def iter(a: Int, result: Int): Int = {
    if (a > b) result
    else iter(a + 1, oper(result, f(a)))
  }
  iter(a, init)
}

Exercise 5.3.1 – Finding Fixed Points of Functions

Assignment

Given the following code, which contains the "fixed-point finding function" fixedPoint: 
val tolerance = 0.0001

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 sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)
Write a function for cube roots using fixedPoint and averageDamp.

Resolution

object Exercise_05_3_1 {
  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 isCloseEnough(x: Double, y: Double) =
    abs((x - y) / x) <= math.ulp(x)

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

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

  def cbrt(x: Double) =
    fixedPoint(averageDamp(y => (x / (y * y) + 2 * y) / 3))(1.0)

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

  def main(args: Array[String]) {
    assert(isCloseEnough(sqrt(2), math.sqrt(2)))
    assert(isCloseEnough(cbrt(2), math.cbrt(2)))
  }
}

Classes and Objects

Exercises 6.0.1 and 6.0.2 – Implementing Custom Collective Types

Assignment

Given the following code: 
trait IntSet {
        def incl(x: Int): IntSet
        def contains(x: Int): Boolean
}

class EmptySet extends IntSet {
        def contains(x: Int): Boolean = false
        def incl(x: Int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet)
}

class NonEmptySet(elem: Int, left: IntSet, right: IntSet) extends IntSet {
        def contains(x: Int): Boolean =
                if (x < elem) left contains x
                else if (x > elem) right contains x
                else true

        def incl(x: Int): IntSet =
                if (x < elem) new NonEmptySet(elem, left incl x, right)
                else if (x > elem) new NonEmptySet(elem, left, right incl x)
                else this
}
Write methods union and intersection to form the union and intersection between two sets.
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.

Resolution

trait IntSet {
  def incl(x: Int): IntSet

  def contains(x: Int): Boolean

  def append(other: IntSet): IntSet

  def union(other: IntSet): IntSet

  def intersect(other: IntSet): IntSet

  def excl(x: Int): IntSet

  def isEmpty: Boolean

  override def toString: String

  override def hashCode: Int

  override def equals(other: Any): Boolean
}

class EmptySet extends IntSet {
  def contains(x: Int): Boolean = false

  def incl(x: Int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet)

  def append(other: IntSet): IntSet = other

  def union(other: IntSet): IntSet = other

  def intersect(other: IntSet): IntSet = this

  def excl(x: Int): IntSet = this

  def isEmpty: Boolean = true

  override def toString = "_,"

  override def hashCode = 0

  override def equals(other: Any) = {
    other.isInstanceOf[EmptySet]
  }
}

class NonEmptySet(elem: Int, left: IntSet, right: IntSet) extends IntSet {
  def contains(x: Int): Boolean =
    if (x < elem) left contains x
    else if (x > elem) right contains x
    else true

  def incl(x: Int): IntSet =
    if (x < elem) new NonEmptySet(elem, left incl x, right)
    else if (x > elem) new NonEmptySet(elem, left, right incl x)
    else this

  def append(other: IntSet): IntSet = {
    val set = left.append(right.append(other))
    set.incl(elem)
  }

  def union(other: IntSet): IntSet = append(other)

  def intersect(other: IntSet): IntSet = {
    val l = left.intersect(other)
    val r = right.intersect(other)
    val s = l.union(r)
    if (other.contains(elem)) s.incl(elem) else s
  }

  def excl(x: Int): IntSet = {
    if (x < elem) new NonEmptySet(elem, left.excl(x), right)
    else if (x > elem) new NonEmptySet(elem, left, right.excl(x))
    else left.append(right)
  }

  def isEmpty: Boolean = false

  override def toString =
    left.toString + elem + "," + right.toString

  override def hashCode = elem + left.toString.length() - right.toString.length()

  override def equals(other: Any) = {
    other match {
      case that: NonEmptySet =>
        that.toString == toString
      case _ => false
    }
  }
}

Exercise 6.0.3 – Implementing Custom Numeric Types

Assignment

Write an implementation Integer of integer numbers. The implementation should support all operations of class Nat: 
abstract class Nat {
        def isZero: Boolean
        def predecessor: Nat
        def successor: Nat
        def + (that: Nat): Nat
        def - (that: Nat): Nat
}

object Zero extends Nat {
        def isZero: Boolean = true
        def predecessor: Nat = error("negative number")
        def successor: Nat = new Succ(Zero)
        def + (that: Nat): Nat = that
        def - (that: Nat): Nat = if (that.isZero) Zero
                else error("negative number")
}

class Succ(x: Nat) extends Nat {
        def isZero: Boolean = false
        def predecessor: Nat = x
        def successor: Nat = new Succ(this)
        def + (that: Nat): Nat = x + that.successor
        def - (that: Nat): Nat = if (that.isZero) this
                else x - that.predecessor
}
while adding two methods: 
def isPositive: Boolean
def negate: Integer
The first method should return true if the number is positive. The second method should negate the number. Do not use any of Scala’s standard numeric classes in your implementation. (Hint: There are two possible ways to implement Integer. One can either make use the existing implementation of Nat, representing an integer as a natural number and a sign. Or one can generalize the given implementation of Nat to Integer, using the three subclasses Zero for 0, Succ for positive numbers and Pred for negative numbers.)

Resolution

I have no idea how to implement a signed type in Scala, thus have implemented the other option "only". – The toInt method does use one of Scala’s standard numeric classes, but it's just used for testing purposes.
import annotation.tailrec

abstract class Integer {
  def -(that: Integer): Integer

  def +(that: Integer): Integer

  def successor: Integer

  def predecessor: Integer

  def isZero: Boolean

  def isPositive: Boolean

  def negate: Integer

  def toInt: Int
}

object ZeroInteger extends Integer {
  override def isZero: Boolean = true

  override def predecessor: Integer = new NegativeInteger(this)

  override def successor: Integer = new PositiveInteger(this)

  override def +(that: Integer): Integer = that

  override def -(that: Integer): Integer = that.negate

  override def isPositive: Boolean = true

  override def negate: Integer = this

  override def toInt: Int = 0
}

class PositiveInteger(private val pred: Integer) extends Integer {
  override def isZero: Boolean = false

  override def predecessor: Integer = pred

  override def successor: Integer = new PositiveInteger(this)

  override def +(that: Integer): Integer =
    if (that.isZero) this
    else if (that.isPositive) predecessor + that.successor
    else this - that.negate

  override def -(that: Integer): Integer =
    if (that.isZero) this
    else if (that.isPositive) posPlusNegInteger(this, that.negate)
    else posPlusNegInteger(this, that)

  protected def posPlusNegInteger(posInt: Integer, negInt: Integer): Integer = {
    @tailrec def iter(p: Integer, n: Integer): Integer = {
      if (n.isZero) p
      else {
        // A positive integer gets counted down (decreased)
        // by calling its predecessor,
        // a negative one by calling its successor.
        val nextP =
          if (p.isInstanceOf[NegativeInteger]) p.successor
          else p.predecessor
        iter(nextP, n.predecessor)
      }
    }

    iter(posInt, negInt)
  }

  override def isPositive: Boolean = true

  override def negate: Integer = new NegativeInteger(predecessor.negate)

  override def toInt: Int = {
    @tailrec def toInt(tempPred: Integer, result: Int): Int = {
      if (tempPred.isZero) result
      else toInt(tempPred.predecessor, result + 1)
    }

    toInt(pred, 1)
  }
}

class NegativeInteger(private val pred: Integer) extends Integer {
  override def isZero: Boolean = false

  override def predecessor: Integer = pred

  override def successor: Integer = new NegativeInteger(this)

  override def +(that: Integer): Integer =
    if (that.isZero) this
    else if (that.isPositive) that - this
    else predecessor + that.successor

  override def -(that: Integer): Integer =
    if (that.isZero) this
    else if (that.isPositive) pred + that.negate
    else predecessor - that.predecessor

  override def isPositive: Boolean = false

  override def negate: Integer = new PositiveInteger(predecessor.negate)

  override def toInt: Int = {
    @tailrec def toInt(tempPred: Integer, result: Int): Int = {
      if (tempPred.isZero) result
      else toInt(tempPred.predecessor, result - 1)
    }

    toInt(pred, -1)
  }
}
Jeremy Collins kindly pointed out that the above method of negating an integer (the method posPlusNegInteger(..)) was unnecessarily complex (d'uh!) if we'd pass a related Integer to the constructor (although I'm not sure whether the assignment allows that). – Here's his alternative solution – thanks, Jeremy:
abstract class Integer(n: Int) {
  def isZero: Boolean
  def isPositive: Boolean
  def predecessor: Integer
  def successor: Integer
  def + (that: Integer): Integer
  def - (that: Integer): Integer
  def negate: Integer
  final override def toString: String = n.toString
}

object IntZero extends Integer(0) {
  def isZero: Boolean = true
  def isPositive: Boolean = false
  def predecessor: Integer = new NegInt(this, -1)
  def successor: Integer = new PosInt(this, 1)
  def + (that: Integer): Integer = that
  def - (that: Integer): Integer = {
    def iter(n: Integer, p: Integer): Integer = {
      if (n.isZero) p
      else {
        val nextN = if (n.isPositive) n.predecessor else n.successor
        val nextP = if (n.isPositive) p.predecessor else p.successor
        iter(nextN, nextP)
      }
    }
    iter(that, this)
  }
  def negate: Integer = this
}

class PosInt(last: Integer, n: Int) extends Integer(n: Int) {
  def isZero: Boolean = false
  def isPositive: Boolean = true
  def predecessor: Integer = last
  def successor: Integer = new PosInt(this, n+1)
  def +(that: Integer): Integer = last + that.successor
  def -(that: Integer): Integer = last - that.predecessor
  def negate: Integer = IntZero - this
}

class NegInt(last: Integer, n: Int) extends Integer(n: Int) {
  def isZero: Boolean = false
  def isPositive: Boolean = false
  def predecessor: Integer = new NegInt(this, n-1)
  def successor: Integer = last
  def +(that: Integer): Integer = last + that.predecessor
  def -(that: Integer): Integer = last - that.successor
  def negate: Integer = IntZero - this
}

Case Classes and Pattern Matching

Exercise 7.2.2 – Implementing Case Classes and Pattern Matching

Assignment

Consider the following definitions representing trees of integers. These definitions can be seen as an alternative representation of IntSet: 
abstract class IntTree
case object EmptyTree extends IntTree
case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree
Complete the following implementations of function contains and insert for IntTree’s. 
def contains(t: IntTree, v: Int): Boolean = t match { ...
        ...
}
def insert(t: IntTree, v: Int): IntTree = t match { ...
        ...
}

Resolution

sealed abstract class IntTree

case object EmptyTree extends IntTree

case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree

class MyIntTree {
  def contains(t: IntTree, v: Int): Boolean = t match {
    case EmptyTree                  => false
    case Node(e, _, _)  if e == v   => true
    case Node(e, l, _)  if e < v    => contains(l, v)
    case Node(e, _, r)              => contains(r, v)
  }

  /*
  def contains(t: IntTree, v: Int): Boolean = t match {
    case EmptyTree => false
    case Node(elem: Int, left: IntTree, right: IntTree) =>
      if (v == elem) true
      else if (v < elem) contains(left, v)
      else contains(right, v)
  }
  */

  def insert(t: IntTree, v: Int): IntTree = t match {
    case EmptyTree => new Node(v, EmptyTree, EmptyTree)
    case Node(elem: Int, left: IntTree, right: IntTree) =>
      if (v < elem) new Node(elem, insert(left, v), right)
      else new Node(elem, left, insert(right, v))
  }
}
There are two versions of the contains method, one of which featuring wildcard placeholders and pattern guards.
Note that both functions, contains and insert – in contrast to our IntSet (see Exercises 6.0.1 and 6.0.2) – do not actually work (except for demonstrating Pattern Matching). To change that we'd need to make the Node's properties accessible. Currently, they aren't because we're accessing the Nodes by their IntTree interface (which we could change, etc. pp.). – Anyways, that's supposedly out of this exercise's scope.

Lists

Exercise 9.1.1 – Implementing a Functional Ordering Algorithm

Assignment

As an example of how lists can be processed, consider sorting the elements of a list of numbers into ascending order. One simple way to do so is insertion sort, which works as follows: To sort a non-empty list with first element x and rest xs, sort the remainder xs and insert the element x at the right position in the result. Sorting an empty list will yield the empty list. Expressed as Scala code: 
def isort(xs: List[Int]): List[Int] =
        if (xs.isEmpty) Nil
        else insert(xs.head, isort(xs.tail))
Provide an implementation of the missing function insert.

Resolution

object Exercise_09_1_1 {
  def isort(xs: List[Int]): List[Int] =
    if (xs.isEmpty) Nil
    else insert(xs.head, isort(xs.tail))

  def insert(x: Int, xs: List[Int]): List[Int] = {
    xs match {
      case List() => List(x)
      case y :: ys =>
        if (x <= y) x :: xs
        else y :: insert(x, ys)
    }
  }

  def main(args: Array[String]) {
    assert(isort(List(3, 5, 1)) == List(1, 3, 5))
  }
}

Exercise 9.2.1 – Another Tail-Recursive Function

Assignment

Given the following function, which computes the length of a list:
def length: Int = this match {
        case Nil => 0
        case x :: xs => 1 + xs.length
}
Design a tail-recursive version of length.

Resolution

import annotation.tailrec

trait PimpedList[T] {
  val xs: List[T]

  def recursiveLength: Int = {
    @tailrec def iter(xs: List[T], acc: Int): Int = {
      xs match {
        case Nil => acc
        case x :: xs => iter(xs, acc + 1)
      }
    }

    iter(xs, 0)
  }
}

object Exercise_09_2_1 {
  implicit def toPimpedList[T](ys: List[T]) = new PimpedList[T] {
    val xs = ys
  }

  def main(args: Array[String]) {
    assert(List().recursiveLength == 0)
    assert(List(1, -2).recursiveLength == 2)
    assert(List(1, 0, 3).recursiveLength == 3)
  }
}
The List class is sealed in Scala and thus cannot be extended. To work around that limitation ;-) , we're employing an implicit conversion to make the recursiveLength method available to the List instance.

Exercise 9.4.1 – Utilizing Higher-Order Methods

Assignment

Consider a function which squares all elements of a list and returns a list with the results. Complete the following two equivalent definitions of squareList. 
def squareList(xs: List[Int]): List[Int] = xs match {
        case List() => ??
        case y :: ys => ??
}
def squareList(xs: List[Int]): List[Int] =
        xs map ??

Resolution

object Exercise_09_4_1 {
  def squareList(xs: List[Int]): List[Int] = xs match {
    case List() => List()
    case y :: ys => math.pow(y, 2).toInt :: squareList(ys)
  }

  def squareList2(xs: List[Int]): List[Int] =
    xs map (x => math.pow(x, 2).toInt)

  def main(args: Array[String]) {
    assert(squareList(List(1, 2, 3)) == List(1, 4, 9))
    assert(squareList2(List(1, 2, 3)) == List(1, 4, 9))
  }
}

Unnamed Exercise (9.4.1 a)) – Understanding List Filtering

Assignment

Considering the following methods of class List: 
def filter(p: A => Boolean): List[A] = this match {
        case Nil => this
        case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p)
}

def forall(p: A => Boolean): Boolean =
        isEmpty || (p(head) && (tail forall p))

def exists(p: A => Boolean): Boolean =
        !isEmpty && (p(head) || (tail exists p))
Define forall and exists in terms of filter.

Resolution

Bruce Gilmour of Lang Toun Software Ltd fixed a logical bug in the forall method. – Thanks Bruce.
object Exercise_09_4_1_a {
  def forall[A](p: A => Boolean)(xs: List[A]): Boolean = {
    def filter[A](p: A => Boolean)(xs: List[A]): List[A] = xs match {
      case Nil => Nil
      case y :: ys => 
        if (p(y)) y :: ys.filter(p) 
        else Nil
    }

    // filter(p)(xs).length > 0
    filter(p)(xs).length == xs.length
  }

  def exists[A](p: A => Boolean)(xs: List[A]): Boolean = {
    def filter[A](p: A => Boolean)(xs: List[A]): List[A] = xs match {
      case Nil => xs
      case y :: ys => 
        if (p(y)) List(y) // found; no need for further recursion
        else ys.filter(p)
    }

    filter(p)(xs).length > 0
  }

  def main(args: Array[String]) {
    // val xs = List(1, 2, 3, 4, 5)
    val xs = List(1, 2, 3, 4, 5, 0)

    assert(exists[Int](x => x > 3)(xs))
    assert(!exists[Int](x => x < 0)(xs))

    // assert(forall[Int](x => x > 0)(xs))
    assert(forall[Int](x => x >= 0)(xs))
    assert(!forall[Int](x => x > 3)(xs))
  }
}

Exercise 9.4.2 – Discussing foldLeft Vs. foldRight in the Context of List Concatenation

Assignment

Consider the problem of writing a function flatten, which takes a list of element lists as arguments. The result of flatten should be the concatenation of all element lists into a single list. Here is an implementation of this method in terms of :\. 
def flatten[A](xs: List[List[A]]): List[A] =
        (xs :\ (Nil: List[A])) {(x, xs) => x ::: xs}
Consider replacing the body of flatten by 
((Nil: List[A]) /: xs) ((xs, x) => xs ::: x)
What would be the difference in asymptotic complexity between the two versions of flatten?

Resolution

First-off, using curly braces ({}) vs. parentheses (()) does not make a difference. For clarity, let's also name the functions accordingly:
def flattenLeft[A](xs: List[List[A]]): List[A] =
  ((Nil: List[A]) /: xs) {
    (xs, x) => xs ::: x
  }

def flattenRight[A](xs: List[List[A]]): List[A] =
  (xs :\ (Nil: List[A])) {
    (x, xs) => x ::: xs
  }
The fold left method (/:, alias of foldLeft) and the fold right method (:\, alias for foldRight) (see the ScalaDocs) both take a start value ((Nil: List[A]) in this case) and an operation ((x, xs) => x ::: xs, resp., (xs, x) => xs ::: x in this case).
The operation that both functions perform is list concatenation via the ::: method.
For operations there is the concept of associativity, which defines on which object the function operates, and which object(s) (if any) it takes as parameters. – Functions whose names end in a colon (:) always associate to the right.
Hence /: operates on a filled List in the above code snippet while :\ operates on an empty one. This defines the order of the parameters that are passed to the function that performs list concatenation via :::.
As ::: associates to the right (xs ::: x can also be expressed as x.:::(xs) using the infix operator .), the flattenLeft method needs to operate on the fully-filled (vs. initially empty) xs: List at each recursion. Considering the design of Scala Lists, this means that flattenLeft has to copy xs.head n - 1 times, where n equals xs.length.
Thus, in this case, flattenRight ought to be preferred because of the costly list concatenation, because that associates right.
A rule of thumb, use foldLeft with left-associating operators and foldRight with right-associating ones.
There's more to say on foldLeft and foldRight. For further information see Programming in Scala – Second Edition, pp. 365 ff., and the following StackOverflow threads: [1] [2] [3].

Exercise 9.4.3 – Realizing Further Usage Options of foldLeft and foldRight

Assignment

Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as fold operations. 
def mapFun[A, B](xs: List[A], f: A => B): List[B] =
        (xs :\ List[B]()){ ?? }

def lengthFun[A](xs: List[A]): Int =
        (0 /: xs){ ?? }

Resolution

object Exercise_09_4_3 {
  def mapFun[A, B](xs: List[A], f: A => B): List[B] =
    (xs :\ List[B]()) {
      (x, xs) => f(x) :: xs
    }

  def lengthFun[A](xs: List[A]): Int =
    (0 /: xs) {
      (sum, _) => sum + 1
    }

  def main(args: Array[String]) {
    val xs: List[Int] = List(1, 2, 3)

    def f(x: Int): Int = math.pow(x, 2).toInt

    assert(lengthFun(xs) == 3)
    assert(mapFun(xs, f) == List(1, 4, 9))
  }
}
The articles Scala Code Review: foldLeft and foldRight and Lots And Lots Of foldLeft Examples help digging deeper into foldLeft and foldRight.

For-Comprehensions

Exercise 10.1.1 – Solving the n-Queens Problem

Assignment

Given a chess board of size n, place n queens on it so that no queen is in check with another. – Considering the code: 
def queens(n: Int): List[List[Int]] = {
        def placeQueens(k: Int): List[List[Int]] =
                if (k == 0) List(List())
                else for { queens <- placeQueens(k - 1)
                        column <- List.range(1, n + 1)
                        if isSafe(column, queens, 1) } yield column :: queens
                placeQueens(n)
}
Write the function 
def isSafe(col: Int, queens: List[Int], delta: Int): Boolean
which tests whether a queen in the given column col is safe with respect to the queens already placed. Here, delta is the difference between the row of the queen to be placed and the row of the first queen in the list.

Resolution

def isSafe(col: Int, queens: List[Int], delta: Int): Boolean =
  queens match {
    case Nil => true
    case List() => true
    case c :: rest =>
      c != col &&
        math.abs(c - col) != delta &&
        isSafe(col, rest, delta + 1)
  }
Note that the queens function – in contrast to the n-Queens solution in Programming in Scala - Second Edition, pp. 519 ff., – returns a List[List[Int]] (i.e., List(List(3, 1, 4, 2), List(2, 4, 1, 3)) for n = 4), where the position on the chess board is marked implicitly – as the order of the inner list items (n - 1 to 0).

Exercise 10.3.1 – Translating foldRight to a for Loop

Assignment

Define the following function in terms of for. 
def flatten[A](xss: List[List[A]]): List[A] =
  (xss :\ (Nil: List[A])) ((xs, ys) => xs ::: ys)

Resolution

object Exercise_10_3_1 {
  def flattenOrg[A](xss: List[List[A]]): List[A] =
    (xss :\ (Nil: List[A]))((xs, ys) => xs ::: ys)

  def flatten[A](xss: List[List[A]]): List[A] =
    for (xs <- xss; x <- xs) yield x

  def main(args: Array[String]) {
    val xss = List(List(1, 2), List(3, 4))

    assert(flatten(xss) == flattenOrg(xss))
  }
}

Exercise 10.3.2 – Translating for Loops to Higher-Order Functions

Assignment

Translate 
for (b <- books; a <- b.authors if a startsWith "Bird") yield b.title
for (b <- books if (b.title indexOf "Program") >= 0) yield b.title
to higher-order functions.

Resolution

object Exercise_10_3_2 {

  case class Book(title: String, authors: String*)

  def main(args: Array[String]) {
    val books: List[Book] =
      List(
        Book(
          "Structure and Interpretation of Computer Programs",
          "Abelson, Harold", "Sussman, Gerald J."
        ),
        Book(
          "Principles of Compiler Design",
          "Aho, Alfred", "Ullman, Jeffrey"
        ),
        Book(
          "Programming in Modula-2",
          "Wirth, Niklaus"
        ),
        Book(
          "Elements of ML Programming",
          "Ullman, Jeffrey"
        ),
        Book(
          "The Java Language Specification", "Gosling, James",
          "Joy, Bill", "Steele, Guy", "Bracha, Gilad"
        )
      )

    val titles1 = for (b <- books; a <- b.authors if a startsWith "Bird") yield b.title
    val titles2 = for (b <- books if (b.title indexOf "Program") >= 0) yield b.title

    assert(titles1.length == 0)
    assert(titles2.length == 3)

    def filter(books: List[Book], cond: Book => Boolean): List[String] =
      books.filter(cond(_)).foldLeft(List[String]()) {
        (titles, book) => book.title :: titles
      }

    val titles1a = filter(books,
      b => b.authors.filter(_.startsWith("Bird")).length > 0)
    val titles2a = filter(books,
      b => (b.title indexOf "Program") >= 0)

    assert(titles1 == titles1a)
    assert(titles2 == titles2a.reverse)
  }
}

Mutable State

Exercise 11.2.1 – Writing a Loop as a Higher-Order Function, Accessing State

Assignment

Given the following function: 
def whileLoop(condition: => Boolean)(command: => Unit) {
        if (condition) {
                command; whileLoop(condition)(command)
        } else ()
}
Write a function repeatLoop, which should be applied as follows: 
repeatLoop { command } ( condition )
Is there also a way to obtain a loop syntax like the following? 
repeatLoop { command } until ( condition )

Resolution

object Exercise_11_2_1 {
  def main(args: Array[String]) {
    var x = 0

    repeatLoop {x = x + 1} (x < 5)
    assert(x == 5)

    repeatLoop {x = x - 1} (until (x == 0))
    assert(x == 0)

    def until(condition: => Boolean): Boolean = !condition

    def repeatLoop(command: => Unit)(condition: => Boolean) {
      if (condition) {
        command
        repeatLoop {command} (condition)
      }
    }
  }
}

Exercise 11.3.1 – Understanding the Discrete Event Simulation Sample

Assignment

Given the concepts bespoken in Scala by Example, pp. 92 ff., and the andGate method: 
def andGate(a1: Wire, a2: Wire, output: Wire) {
  def andAction() {
    val a1Sig = a1.getSignal
    val a2Sig = a2.getSignal
    afterDelay(AndGateDelay) {
      output setSignal (a1Sig & a2Sig)
    }
  }
  a1 addAction andAction
  a2 addAction andAction
}
Write the implementation of orGate.

Resolution

def orGate(a1: Wire, a2: Wire, output: Wire) {
  def orAction() {
    val a1Sig = a1.getSignal
    val a2Sig = a2.getSignal
    afterDelay(OrGateDelay) {
      output setSignal (a1Sig | a2Sig)
    }
  }
  a1 addAction orAction
  a2 addAction orAction
}

Exercise 11.3.2 – Understanding the Discrete Event Simulation Sample

Assignment

Another way is to define an or-gate by a combination of inverters: 
def inverter(input: Wire, output: Wire) {
  def invertAction() {
    val inputSig = input.getSignal
    afterDelay(InverterDelay) {
      output setSignal !inputSig
    }
  }
  input addAction invertAction
}
and and-gates. Define a function orGate in terms of andGate and inverter. What is the delay time of this function?

Resolution

def orGate(a1: Wire, a2: Wire, output: Wire) {
  inverter(a1, output)
  andGate(a1, a2, output)
}
In contrast to the original orGate from exercise 11.3.1, where the delay time is OrGateDelay, here the delay time equals InverterDelay + AndGateDelay.

Hindley/Milner Type Inference

Exercise 16.0.1 – Understanding Hindley/Milner Type Inference

Assignment

Given the code introduced in Scala by Example, pp. 117 ff., extend the Mini-ML type inferencer with a letrec construct which allows the definition of recursive functions. Syntax: 
letrec ident "=" term in term
The typing of letrec is as for let, except that the defined identifier is visible in the defining expression. Using letrec, the length function for lists can now be defined as follows. 
letrec length = \xs.
  if (isEmpty xs)
    zero
  (succ (length (tail xs)))
in ...

Resolution

This is a highly complex assignment, which requires conceptual backgrounds on language design in general and, particularly, on type inference – additionally, requiring outstanding logical skills and efforts.
It appears to be not at all certain whether a resolution would have had been brought up if remarkably exceptional Nada Amin had not provided one.
Please note that this solution may be work in progress. There may be future corrections to the original assignment as well. – Thank you very much, Nada.

Resources

All links retrieved at the date of publication.

Primary Resources

Secondary Resources

Resources on Exercise 16.0.1

"The" Resolution

Other Resources


Valid XHTML 1.0 Transitional Valid CSS!