Scala By Example Chapter 11 Solutions - Exercise 11.3.2

Exercise 11.3.2 Another way is to define an or-gate by a combination of inverters and and gates. Define a function orGate in terms of andGate and inverter. What is the delay time of this function?

The delay parameter has also been left unused in this case. However it would not be difficult to conclude that the delay time for this function would be = inverter delay time + AND delay time + inverter delay time = 2 (inverter delay) + AND delay.

	object CompoundOrGate {
	type Action = () => Unit
	class Wire {
	private var sigVal = false
	private var actions: List[Action] = List()
	def getSignal = sigVal
	def setSignal(s: Boolean) =
	if (s != sigVal) {
	sigVal = s
	actions.foreach(action => action())
	}
	def addAction(a: Action) {
	actions = a :: actions; a()
	}
	}
	//The delay parameter is not used.
	def afterDelay(delay: Int)(block: => Unit) = block
	def inverter(input: Wire, output: Wire) {
	def invertAction() {
	val inputSig = input.getSignal
	afterDelay(0) { output setSignal !inputSig }
	}
	input addAction invertAction
	}
	def andGate(input1: Wire, input2: Wire, output: Wire) {
	def andAction() {
	val inputSig1 = input1.getSignal
	val inputSig2 = input2.getSignal
	afterDelay(0) { output setSignal inputSig1 & inputSig2 }
	}
	input1 addAction andAction
	input2 addAction andAction
	}
	def orGate(input1: Wire, input2: Wire, output: Wire) {
	def orAction() {
	val inputSig1 = input1.getSignal
	val inputSig2 = input2.getSignal
	afterDelay(0) { output setSignal inputSig1 | inputSig2 }
	}
	input1 addAction orAction
	input2 addAction orAction
	}
	def compoundOrGate(input1: Wire, input2: Wire, output: Wire) {
	val o1, o2, o3 = new Wire
	inverter(input1, o1)
	inverter(input2, o2)
	andGate(o1, o2, o3)
	inverter(o3, output)
	}
	def main(args: Array[String]) {
	val inp1, inp2, output = new Wire
	inp1.setSignal(true)
	inp2.setSignal(false)
	compoundOrGate(inp1, inp2, output)
	println("Output of compound OR gate is: " + output.getSignal)
	}
	}

view raw CompoundOrGate.scala hosted with ❤ by GitHub

Scala By Example Chapter 11 Solutions - Exercise 11.3.1

Exercise 11.3.1 Write the implementation of orGate.

Note that the delay parameter in the function afterDelay has not been used since it removes complexity when testing this case.

	object SimpleOrGate {
	type Action = () => Unit
	class Wire {
	private var sigVal = false
	private var actions: List[Action] = List()
	def getSignal = sigVal
	def setSignal(s: Boolean) =
	if (s != sigVal) {
	sigVal = s
	actions.foreach(action => action())
	}
	def addAction(a: Action) {
	actions = a :: actions; a()
	}
	}
	//The delay parameter is not used.
	def afterDelay(delay: Int)(block: => Unit) = block
	def inverter(input: Wire, output: Wire) {
	def invertAction() {
	val inputSig = input.getSignal
	afterDelay(0) { output setSignal !inputSig }
	}
	input addAction invertAction
	}
	def orGate(input1: Wire, input2: Wire, output: Wire) {
	def orAction() {
	val inputSig1 = input1.getSignal
	val inputSig2 = input2.getSignal
	afterDelay(0) { output setSignal inputSig1 | inputSig2 }
	}
	input1 addAction orAction
	input2 addAction orAction
	}
	def main(args: Array[String]) {
	val inp1, inp2, output = new Wire
	inp1.setSignal(true)
	inp2.setSignal(false)
	orGate(inp1, inp2, output)
	println("Output of simple OR gate is: " + output.getSignal)
	}
	}

view raw SimpleOrGate.scala hosted with ❤ by GitHub

Scala By Example Chapter 11 Solutions - Exercise 11.2.1

Exercise 11.2.1 Write a function repeatLoop with also additional syntax for an until clause.

The repeat { command } until (condition) was tricky. The trick is to realize that "until" would be a method call, and for it to be a method call, "repeat {command}" would have to be an object. Since objects are created using new, we could wrap this object creation with a method. The result is below. Note that the second method has been changed to repeatUntilLoop since it would conflict with the previous method repeatUntil.

	object FunctionalLoops {
	def repeatLoop(command: => Unit)(condition: => Boolean) {
	command
	if (condition) {
	repeatLoop(command)(condition)
	} else ()
	}
	def repeatUntilLoop(command: => Unit) = {
	class RepeatUntilLoopClass(command: => Unit) {
	def until(condition: => Boolean): Unit = {
	command
	if (!condition) {
	until(condition)
	} else ()
	}
	}
	new RepeatUntilLoopClass(command)
	}
	def main(args: Array[String]) {
	var i = 10;
	repeatLoop { i -= 1; println(i) } (i > 0)
	var j = 1;
	repeatUntilLoop { j += 10; println(j) } until (j >= 100)
	}
	}

view raw FunctionalLoops.scala hosted with ❤ by GitHub

Scala By Example Chapter 10 Solutions - Exercise 10.3.2

Exercise 10.3.2 Translate the following for comprehensions to higher-order functions.

	object ForToMap {
	def main(args: Array[String]) {
	case class Book(title: String, authors: List[String])
	val books: List[Book] = List(
	Book("Structure and Interpretation of Computer Programs",
	List("Abelson, Harold", "Sussman, Gerald J.")),
	Book("Principles of Compiler Design",
	List("Aho, Alfred", "Ullman, Jeffrey")),
	Book("Programming in Modula2",
	List("Wirth, Niklaus")),
	Book("Introduction to Functional Programming",
	List("Bird, Richard")),
	Book("The Java Language Specification",
	List("Gosling, James", "Joy, Bill", "Steele, Guy", "Bracha, Gilad")))
	println("All books with authors starting with the word 'Bird': " +
	books.flatMap(b => b.authors.filter(a => a startsWith "Bird").map(a => b.title)))
	println("All books with the word 'Program' in it: " +
	books.filter(b => (b.title indexOf "Program") >= 0).map(b => b.title))
	}
	}

view raw ForToMap.scala hosted with ❤ by GitHub

Scala By Example Chapter 10 Solutions - Exercise 10.3.1

Exercise 10.3.1 Define the following function in terms of for.

This will be revisited later.

Scala By Example Chapter 10 Solutions - Exercise 10.1.1

Exercise10.1.1 Write the function isSafe.

	object NQueensProblem {
	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)
	}
	def isSafe(col: Int, queens: List[Int], delta: Int): Boolean = queens match {
	case Nil => true
	case x :: xs => col != x && col != x - delta && col != x + delta &&
	isSafe(col, xs, delta + 1)
	}
	def main(args: Array[String]) {
	println ("Solving nqueens: ")
	val x = queens(8)
	println("Number of solutions: " + x.length)
	println(x)
	}
	}

view raw NQueensProblem.scala hosted with ❤ by GitHub

Scala By Example Chapter 9 Solutions - Exercise 9.4.3

Exercise 9.4.3 Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as fold operations.

This will be revisited later.

Scala By Example Chapter 9 Solutions - Exercise 9.4.2

Exercise 9.4.2 What would be the difference in asymptotic complexity between the two versions of flatten?

This will be revisited later.

Scala By Example Chapter 9 Solutions - Unnamed Exercise after 9.4.1

Exercise: Define forall and exists in terms of filter.

As before, since class List cannot be extended in scala, the methods are implemented as pure functions taking a list parameter.

	object ListFilter {
	def forall(xs: List[Int], p: Int => Boolean): Boolean =
	xs.isEmpty || xs.filter(p) == xs
	def exists(xs: List[Int], p: Int => Boolean): Boolean =
	!xs.isEmpty && !xs.filter(p).isEmpty
	def main(args: Array[String]) {
	println("Are members of list (1,2,3,4,5) less than 10? : " +
	forall(List(1,2,3,4,5), (x => x < 10)));
	println("Is there at least one member of list (1,2,3,4,5) thats greater than 5? : " +
	exists(List(1,2,3,4,5), (x => x > 5)));
	}
	}

view raw ListFilter.scala hosted with ❤ by GitHub

Scala By Example Chapter 9 Solutions - Exercise 9.4.1

Exercise 9.4.1 Consider a function which squares all elements of a list and re- turns a list with the results. Complete the following two equivalent definitions of squareList.

	object ListMap {
	def squareList(xs: List[Int]): List[Int] = xs match {
	case List() => xs
	case y :: ys => y * y :: squareList(ys)
	}
	def squareListMap(xs: List[Int]): List[Int] =
	xs map (x => x * x)
	def main(args: Array[String]) {
	println("squarelist for square of (9,13,21) returns : " + squareList(List(9, 13, 21)));
	println("squareListMap for square of (9,13,21) returns : " + squareList(List(9, 13, 21)));
	}
	}

view raw ListMap.scala hosted with ❤ by GitHub