This is the second in a series of articles working though the exercises in Brian Marick’s Functional Programming for the Object-Oriented Programmer, but implemented in Scala instead of Clojure. (Hat tip to Mr. Avdi Grimm for the idea.) The full source code is available on GitHub. Read the previous article on the exercises in chapter 1.
Exercise 1: Factorial
We did a factorial function in chapter 1, but Mr. Marick introduces us to recursion in chapter 6. Therefore we’ll use recursion in this implementation, in particular, recursion that uses the following form:
def factorial(n: Int): Int = n match {
case endingCase => endingValue(n)
case _ => combine(n, factorial(smallerValFromN(n)))
}
As with last time, the test first using the table-driven method:
class FactorialSpec extends UnitSpec with TableDrivenPropertyChecks {
"Chapter 6, Exercise 1: factorial" should "compute the factorial, i.e., n!, of a given integer n >= 0" in {
val factorials = Table(
("n", "fact"),
(0, 1),
(1, 1),
(2, 2),
(3, 6),
(4, 24),
(5, 120)
)
forAll (factorials) { (n: Int, fact: Int) =>
whenever (n >= 0) {
factorial(n) should be (fact)
}
}
}
}
… and now the implementation:
object Chapter06 {
def factorial(n: Int): Int = n match {
case 0 => 1
case _ => n * factorial(n - 1)
}
}
In one of Mr. Marick’s hints, he suggests not worrying about the zero case, but it’s easy enough. Another case to handle is a negative n, which I handled in the exercises for chapter 1, but decided not to bother with this time.
Exercise 2: A Second Factorial
Yet another implementation of factorial, but this time we use a slightly different recursive form:
def factorial(n: Int): Int = {
def factorialAcc(n: Int, soFar: Int) = n match {
case endingCase => soFar
case _ => factorialAcc(smallerValFromN(n), combine(n, soFar))
}
factorialAcc(n, 1)
}
My test is almost exactly the same as the test for Exercise #1:
class Factorial2Spec extends UnitSpec with TableDrivenPropertyChecks {
"Chapter 6, Exercise 2: factorial2" should "compute the factorial, i.e., n!, of a given integer n >= 0" in {
val factorials = Table(
("n", "fact"),
(0, 1),
(1, 1),
(2, 2),
(3, 6),
(4, 24),
(5, 120)
)
forAll (factorials) { (n: Int, fact: Int) =>
whenever (n >= 0) {
factorial2(n) should be (fact)
}
}
}
}
The implementation using the second form of recursion is as follows:
object Chapter06 {
def factorial2(n: Int): Int = {
@tailrec
def fact_(something: Int, soFar: Int): Int = something match {
case 0 => soFar
case _ => fact_(something - 1, something * soFar)
}
fact_(n, 1)
}
}
Two points about this form of recursion: First, this form uses an accumulator, a value that we use to build our way up to the final answer with each step of the recursion (in contrast to the first pattern, which piles up a stack of recursive calls until the end case, at which point we combine the return values of the entire stack). The soFar parameter of the fact_ inner function serves as the accumulator in the implementation above.
Second, this form of recursion uses tail recursion, wherein the return value on the recursive branch is the recursive call and nothing else. The call to fact_ in the recursive branch is called a tail call. The compiler can optimize tail recursion as a loop. As Mr. Marick informs us, in Clojure, one must employ the recur function to make tail call optimization happen. Similarly, Scala requires the @tailrec annotation, as highlighted above.
Exercise 3: Summing a Sequence of Numbers
This exercise is to implement a function that sums the number of a sequence together using the second pattern of recursion, i.e., using a tail call with an accumulator. The test is as follows:
class SumSequenceSpec extends UnitSpec {
"Chapter 6, Exercise 3: sumSequence" should "sum all of the elements in a sequence starting with an initial value" in {
sumSequence(Seq(2, 4, 6, 8), 0) should be (20)
}
it should "return 0 if the sequence is empty" in {
sumSequence(Seq[Int](), 0) should be (0)
}
}
… and the implementation:
object Chapter06 {
@tailrec
def sumSequence[T](seq: Seq[T], init: T)(implicit n: Numeric[T]): T = seq match {
case Seq() => init
case _ => sumSequence(seq.tail, n.plus(init, seq.head))
}
}
This time, instead of using an inner function to do the recursion, sumSequence itself takes an accumulator, init. Consequently, I can annotate it with @tailrec. Also I employed the trick from the exercises in chapter 1 of using an implicit Numeric parameter to enforce the constraint that this only works for sequences of numbers.
Exercise 4: Multiplying a Sequence of Numbers
The only difference between this exercise and the last one is the operation we perform on the sequence elements. Here’s the test:
class ProdSequenceSpec extends UnitSpec {
"Chapter 6, Exercise 4: prodSequence" should "multiply all of the elements in a sequence starting with an initial value" in {
prodSequence(Seq(2, 4, 6, 8), 1) should be (384)
}
it should "return 1 if the sequence is empty" in {
prodSequence(Seq[Int](), 1) should be (1)
}
}
… and here’s the implementation:
object Chapter06 {
@tailrec
def prodSequence[T](seq: Seq[T], init: T)(implicit n: Numeric[T]): T = seq match {
case Seq() => init
case _ => prodSequence(seq.tail, n.times(init, seq.head))
}
}
Exercise 4a: Extracting the Combiner
Mr. Marick notes that the only difference between exercises 3 and 4 is the operation performed on the elements in the sequence, or the combiner, to borrow the parlance in Mr. Marick’s pseudocode. The test reflects the difference in the way we call the function now by passing in the combiner as a parameter with the sequence:
class ReduceSequenceSpec extends UnitSpec {
val op = (a: Int, b: Int) => a * b
"Chapter 6, Exercise 4a: reduceSequence" should "apply an operation all of the elements in a sequence starting with an initial value" in {
reduceSequence(op, Seq(2, 4, 6, 8), 1) should be (384)
}
it should "return init if the sequence is empty" in {
reduceSequence(op, Seq[Int](), 1) should be (1)
}
}
And here is how I have implemented it:
object Chapter06 {
@tailrec
def reduceSequence[A](op: (A, A) => A, seq: Seq[A], init: A): A = seq match {
case Seq() => init
case _ => reduceSequence(op, seq.tail, op(seq.head, init))
}
}
That works, but there is a problem. Exercise 5 exposes it.
Exercise 5: Building a Map from a Sequence
Mr. Marick stresses that we should perform this next exercise without changing the implementation of reduceSequence. So let’s try with our test:
class ReduceSequenceVecToMapSpec extends UnitSpec {
val op = (a: String, b: Map[String, Int]) => b + (a -> 0)
"Chapter 6, Exercise 5: reduceSequence" should "convert a sequence of strings into a map keyed to those strings with values of zero" in {
reduceSequence(op, Vector("a", "b", "c"), Map[String, Int]()) should be (Map("a" -> 0, "b" -> 0, "c" -> 0))
}
it should "return init if the sequence is empty" in {
reduceSequence(op, Seq[String](), Map[String, Int]()) should be (Map[String, Int]())
}
val op2 = (a: String, b: Map[String, Int]) => b + (a -> (b.size + 1))
"Chapter 6, Exercise 5a: reduceSequence" should "convert a sequence of strings into a map keyed to those strings with values that increment by 1" in {
reduceSequence(op2, Vector("a", "b", "c"), Map[String, Int]()) should be (Map("a" -> 1, "b" -> 2, "c" -> 3))
}
}
And now the error bites us. Clojure is dynamically typed, so the implementation we would have come up with in Clojure probably would still work for this exercise if it worked for the last one.
Scala, in contrast, is statically typed. Our implementation worked in the last exercise because the type of the elements in the input sequence is the same as the type of the return value: we’re taking a sequence of integers and multiplying/adding them together, which produces an integer. In this exercise, however, we need to take a sequence of strings and produce a map—ain’t nothin’ the same about them types there! Therefore the implementation has to change to allow for a return type different from the type of the input elements:
object Chapter06 {
@tailrec
def reduceSequence[A, B](op: (A, B) => B, seq: Seq[A], init: B): B = seq match {
case Seq() => init
case _ => reduceSequence(op, seq.tail, op(seq.head, init))
}
}
That wraps up chapter 6. Exercises from later chapters to come in future posts.