May 30, 2011 · Robert Söding

Updated, October 29, 2012

Updated, October 29, 2012

The update affects exercise 9.4.1 a.

Updated, November 16, 2011

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.

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.

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.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) } }

Trace the execution of the

`sqrt(4)`

expression.Using the *root* of the

`improve`

method, `guess`

gets
successively approximated to 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.

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`

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

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)resultelse 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) } }

Write a function

`product`

that computes the
product of the values of functions at points over a given
range.import annotation.tailrec object Exercise_05_2_2 extends Exercise_05_2_x { def linearProduct(a: Int, b: Int): Int = if (a > b)1else a*linearProduct(a + 1, b) defproduct(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)) } }

Write

`factorial`

in terms of
`product`

.In my understanding, "in terms of *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`

" means,
computing "the product of the values of functions at points over a
`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 *factorial* except there are two variable (non-fixed)
bounds, not one.

`product`

equals a
Can you write an even more general function which generalizes
both

`sum`

and `product`

?We're introducing a function parameter that takes a function
itself:

defoperate(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) }

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`

.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))) } }

Given the following code:

Add a method

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: Booleanfor sets.

trait IntSet{ def incl(x: Int): IntSet def contains(x: Int): Boolean def append(other: IntSet): IntSetdef union(other: IntSet): IntSet def intersect(other: IntSet): IntSet def excl(x: Int): IntSet def isEmpty: Booleanoverride 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 = otherdef union(other: IntSet): IntSet = other def intersect(other: IntSet): IntSet = this def excl(x: Int): IntSet = this def isEmpty: Boolean = trueoverride 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 thisdef 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 = falseoverride 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 } } }

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: IntegerThe 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.)I have no idea how to implement a *signed* type in
Scala, thus have implemented the other option "only". – The
*does* use one of Scala’s standard
numeric classes, but it's just used for testing purposes.

`toInt`

method import annotation.tailrecabstract 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 }objectZeroIntegerextends 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 } classPositiveInteger(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) } } classNegativeInteger(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
*d'uh!*) if we'd pass a related

`posPlusNegInteger(..)`

) was unnecessarily complex
(`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 }

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 IntTreeComplete 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 { ... ... }

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 *wildcard placeholders* and
*pattern guards*.

`contains`

method,
one of which featuring Note that both functions, *not* actually work (except for demonstrating Pattern
Matching). To change that we'd need to make the

`contains`

and `insert`

– in contrast to our `IntSet`

(see Exercises 6.0.1 and 6.0.2) – do
`Node`

's
properties accessible. Currently, they aren't because we're
accessing the `Node`

s by their `IntTree`

interface (which we could change, etc. pp.). – Anyways, that's
supposedly out of this exercise's scope.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`

.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)) } }

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`

.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 *implicit
conversion* to make the

`List`

class is
`sealed`

in Scala and thus cannot be extended. To work
around that limitation ;-) , we're employing an `recursiveLength`

method
available to the `List`

instance.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 ??

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)) } }

Considering the following methods of class

`List`

:
defDefinefilter(p: A => Boolean): List[A] = this match { case Nil => this case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p) } defforall(p: A => Boolean): Boolean = isEmpty || (p(head) && (tail forall p)) defexists(p: A => Boolean): Boolean = !isEmpty && (p(head) || (tail exists p))

`forall`

and `exists`

in terms of
`filter`

.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 => Nilcase y :: ys => if (p(y)) y :: ys.filter(p)else Nil} //~~filter(p)(xs).~~filter(p)(xs).length > 0length == 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)) } }

`foldLeft`

Vs.
`foldRight`

in the Context of List ConcatenationConsider 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`

?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 (*fold right* method
(*start
value* (*operation* (

`/:`

, alias of
`foldLeft`

) and the `:\`

, alias for `foldRight`

) (see the
ScalaDocs) both take a `(Nil: List[A])`

in this case) and an
`(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 *filled*
*empty* one. This defines the order of the
parameters that are passed to the function that performs list
concatenation via

`/:`

operates on a `List`

in the above code snippet while `:\`

operates on an `:::`

.As *infix operator*

`:::`

associates to the right (```
xs :::
x
```

can also be expressed as `x.:::(xs)`

using the
`.`

), the
`flattenLeft`

method needs to operate on the
fully-filled (vs. initially empty) `xs: List`

at each
recursion. Considering the design of Scala `List`

s, this
means that `flattenLeft`

has to copy
`xs.head`

`n - 1`

times, where `n`

equals `xs.length`

.Thus, in this case, *costly list concatenation*,
because that *associates right*.

`flattenRight`

ought to be
preferred because of the A rule of thumb, use
*left-associating operators* and
*right-associating* ones.

`foldLeft`

with `foldRight`

with There's more to say on *Programming
in Scala – Second Edition*, pp. 365 ff., and the following
StackOverflow threads: [1] [2] [3].

`foldLeft`

and
`foldRight`

. For further information see `foldLeft`

and `foldRight`

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){ ?? }

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`

.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): Booleanwhich 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.

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 *Programming in Scala -
Second Edition*, pp. 519 ff., – returns a

`queens`

function – in
contrast to the n-Queens solution in `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`

).`foldRight`

to a
`for`

LoopDefine the following function in terms of

`for`

.
def flatten[A](xss: List[List[A]]): List[A] = (xss :\ (Nil: List[A])) ((xs, ys) => xs ::: ys)

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 xdef main(args: Array[String]) { val xss = List(List(1, 2), List(3, 4)) assert(flatten(xss) == flattenOrg(xss)) } }

`for`

Loops to
Higher-Order FunctionsTranslate

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

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) } }

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 )

object Exercise_11_2_1 { def main(args: Array[String]) { var x = 0repeatLoop {x = x + 1} (x < 5)assert(x == 5) repeatLoop {x = x - 1} (until(x == 0)) assert(x == 0)def until(condition: => Boolean): Boolean = !conditiondef repeatLoop(command: => Unit)(condition: => Boolean){ if (condition) { command repeatLoop {command} (condition) } } } }

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`

.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 }

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?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`

.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 termThe 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 ...

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.

All links retrieved at the date of
publication.

- Odersky, Martin; Spoon, Lex; Venners, Bill:
*Programming in Scala – Second Edition*, Artima Press, 2010 - Odersky, Martin: Scala By Example, www.scala-lang.org, 2010

- Allen, Ian D.: Floating Point Encoding, teaching.idallen.org, 2011
- Flierl, Thomas, et al.: question on square root exercise (4.4.1) of ScalaByExample, nabble.com, 2010
- Foltrigg, Bob:
*Solutions to exercises 4.6.1 and 5.2.1*, diamondinheritance.blogspot.com, 2007 - Malone, Matt: Lots And Lots Of foldLeft Examples, oldfashionedsoftware.com, 2009
- Malone, Matt: Scala Code Review: foldLeft and foldRight, oldfashionedsoftware.com, 2009
- Oracle, Inc.: java.lang.Math ApiDoc, download.oracle.com, 2011
- Sroka, J.: Zajęcia nr 5 (
*solutions to exercises 10.1.1 through 11.2.1; in Polish*), www.mimuw.edu.pl, 2009 - Stack Exchange, Inc. (Edt.):
*Discussions on the foldLeft and foldRight Methods*[1] [2] [3], stackoverflow.com, 2009-2010 - Stack Exchange, Inc. (Edt.): Use of recursion in Scala when run in the JVM, stackoverflow.com, 2011
- whiter4bbit: scala_by_example (
*solutions to exercises 4.4.1 through 9.4.1*), github.com, 2009 - Wikimedia Foundation, Inc. (Edt.): Floating Point: Accuracy Problems, en.wikipedia.org, 2011

- Amin, Nada: spots/hindleyMilner/typeInference.scala, github.com, 2011
- namin: implementing type inference, stackoverflow.com, 2009

- Alessi, Fabio: Type preorders and recursive terms
(
*regarding the "fixed point operator*), Elsevier Science B. V., 2004`fix`

, which can be used to represent recursion"; also mentions the`letrec`

typing rule (vs.`let rec`

) - Elsman, Martin: A Portable Standard ML Implementation, Technical University of Denmark, 1994
- Fix, Jim: Homework 7: MiniML type inference
(
*assignment*), people.reed.edu, 2010 - Fix, Jim: Homework 7: MiniML type inference
(
*template code in Scala – unfortunately, using Scala 2.9, throws a runtime error with the basic sample it ships*), people.reed.edu, 2010 - Fix, Jim: The MiniML Programming Language (with substitution semantics), people.reed.edu, 2010
- Forrest, Andrew: Hindley-Milner type inference in Scala
(
*implementation similar to Odersky's – unfortunately, throws a runtime error with Scala 2.9, but works with 2.7.7*), dysphoria.net, 2009 - Khamsi, Mohamed A.; Knaust, Helmut: The Newton-Raphson Method, www.sosmath.com, 201
- Wikimedia Foundation, Inc. (Edt.): ML (programming language), en.wikipedia.org, 2011
- Wikimedia Foundation, Inc. (Edt.): Newton's method, en.wikipedia.org, 2011