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

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

Scala quicksort

Here's a version of quicksort in Scala that I took from the excellent "Scala by Example" pdf from the scala website. The main algorithm is intact; I just thought it would be nice to get a print out of the steps being performed. So basically the program has been changed to include a few extra variables so that their value can be printed to the console. The unsorted input array has been hard-coded into the program just to avoid writing additional code to parse input arguments.

If you have scala installed, you can copy and paste the code to a file, compile it (scalac filename), run (scala compiledfilename) and see the output. Enjoy!

	object QuickSort {
	def sort(xs: Array[Int]): Array[Int] = {
	if (xs.length <= 1) xs
	else {
	val pivot = xs(xs.length / 2)
	val lessThanPivot = xs filter (pivot >)
	val equalToPivot = xs filter (pivot ==)
	val greaterThanPivot = xs filter (pivot <)
	println("Pivot for array [%s] is %d".format(xs.deep.mkString(" "),
	pivot))
	println("[%s] [%s] [%s]\n".format(lessThanPivot.deep.mkString(" "),
	equalToPivot.deep.mkString(" "),
	greaterThanPivot.deep.mkString(" ")))
	Array.concat(sort(lessThanPivot), equalToPivot, sort(greaterThanPivot))
	}
	}
	def main(args: Array[String]) {
	val inputArray = Array(10,9,8,3,7,6,5,4,3,2,1)
	println("Input Array : [%s]\n".format(inputArray.deep.mkString(" ")))
	println("Sorted Array: [%s]".format(sort(inputArray).deep.mkString(" ")))
	}
	}

view raw scala_quicksort.scala hosted with ❤ by GitHub

Scala, Python and language bias

The wonderful Scala by Example pdf by the creator Martin Odersky himself has a quicksort program written in Scala. Its a beautiful piece of succinct code that lays clearly the quicksort algorithm. I started digging into Scala a couple of months back and being a lover of Python, the fact that it didnt need semicolons for indentation was a pleasure to see. As I dug into it further, it seemed I was learning some very new concepts, which I hadnt learned in a while sticking to languages like Java, .NET and even Python. The concept of Actors, Case Classes with pattern matching, parametric classes, variances to name a few were extremely delightful to learn.

One more thing that was really interesting to learn about was the type system. Coming from languages where the concept of types exposed were mainly primitive types and objects, the concept of a type being much more than that was eye-opening.

I have also heard a lot of good things about Clojure, a lisp that runs on the jvm. Just like people gravitated towards Python or Ruby when they became popular, it seems like the same thing is happening with Scala and Clojure. I discovered Python before Ruby and when exploring Python I was so enamoured with the functionality, the ease of programming and the productivity that when I looked at Ruby, it had to be something a lot more than Python for it to catch my eye.

So one could say I was looking at Ruby with a "language(python) bias". So that was mainly what nudged me into the Python camp. I see the same happening with Scala now. I tried it out first, and it seems like it could teach me so much that I would like to be in the Scala camp for now. And "for now" has a good chance of being "forever".

Practical Django projects - Continuing with the CMS

- The admin application's templates can be changed. By default the admin application looks for a template first in the added application directory itself (flatpages application in this case).If not available, then it looks at the directories of the admin application.

- Created a new app for search. This will need an app created using 'manage.py search' since its a separate app and needs a model.

- Strangely, you can invoke any python code as a view function on your computer, even one that's not in INSTALLED_APPS as long as it can be found by django. If that python code needs a model though, it has to go in INSTALLED_APPS.

- Filter method on model objects has argument string built as "__=" and returns list of model objects.

- Template object is created using the path to the html file as parameter. The template is rendered by using a Context object as parameter which is a dictionary with variable name as dict key and variable value as dict value. These variables can be accessed in the html template file using Django template syntax.

- django.shortcuts.render_to_response is a useful facade to just take html file and a dictionary of parameters to do all the above.

- You can change the way the editing for a model object is rendered in the admin app. This has a clear api where you unregister the existing admin class for model and then subclass the admin class with a customized model. Once this is done, you re-register the new admin class for the same model.

- django.http.HttpResponseRedirect is a useful helper method if you want to redirect the results of a model object search to a specific url.