FPOO Chapter 1 in Scala

This is the first 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.

For each exercise, I first wrote a specification in ScalaTest and then wrote the implementation. I followed the recommendation of the ScalaTest user guide and created the UnitSpec base class that all of my specs extend:

class UnitSpec extends FlatSpec
  with Matchers
  with OptionValues
  with Inside

Exercise 1: second

First the test:

class SecondSpec extends UnitSpec {
  "Exercise 1: second" should "return the second item in a given list" in {
    val list = List("Lorem", "ipsum", "dolor", "sit", "amet")
    second(list) should be ("ipsum")
  }
  it should "throw IndexOutOfBoundsException if called on a list with fewer than 2 elements" in {
    val listOf1 = List("sole")
    a [IndexOutOfBoundsException] should be thrownBy {
      second(listOf1)
    }
  }
}

â€¦Â and then the implementation—pretty simple:

object Chapter01 {
  def second[A](list: List[A]): A = list(1)
}

Exercise 2: third

Mr. Marick asked for two implementations. First the tests, then the implementations:

class ThirdSpec extends UnitSpec {
  "Exercise 2a: third" should "return the third item in a given list" in {
    val list = List("Lorem", "ipsum", "dolor", "sit", "amet")
    third(list) should be ("dolor")
  }
  it should "throw IndexOutOfBoundsException if called on a list with fewer than 3 elements" in {
    val listOf2 = List("penultimate", "ultimate")
    a [IndexOutOfBoundsException] should be thrownBy {
      third(listOf2)
    }
  }
 
  "Exercise 2b: third2" should "return the third item in a given list" in {
    val list = List("Lorem", "ipsum", "dolor", "sit", "amet")
    third2(list) should be ("dolor")
  }
  it should "throw NoSuchElementException if called on a list with fewer than 3 elements" in {
    val listOf2 = List("penultimate", "ultimate")
    a [NoSuchElementException] should be thrownBy {
      third2(listOf2)
    }
  }
}

Again, both are pretty simple:

object Chapter01 {
  def third[A](list: List[A]): A = list(2)
  def third2[A](list: List[A]): A = list.tail.tail.head
}

Exercise 3: addSquares

The test for this one is pretty straightforward:

class AddSquaresSpec extends UnitSpec {
  "Exercise 3: addSquares" should "square each item in a list and sum them" in {
    val list = List(1, 2, 5)
    addSquares(list) should be (30)
  }
  it should "return 0 if called on an empty list" in {
    val emptyList = List[Int]()
    addSquares(emptyList) should be (0)
  }
}

I found the implementation somewhat challenging because I was not sure how to limit my input parameter to be a list of numbers. A second argument list that takes a single implicit parameter did the trick:

object Chapter01 {
  def addSquares[T](list: List[T])(implicit n: Numeric[T]): T =
    list.map( x => n.times(x, x) ).sum
}

Exercise 4: bizarreFactorial

In order to have a list of several inputs and the expected result for each, I used ScalaTest’s TableDrivenPropertyChecks trait.

class BizarreFactorialSpec extends UnitSpec with TableDrivenPropertyChecks {
  "Exercise 4: bizarreFactorial" should "compute the factorial, i.e., n!, of a given integer n >= 0" in {
    val factorials = Table(
      ("n", "factorial"),
      (0,   1),
      (1,   1),
      (2,   2),
      (3,   6),
      (4,  24),
      (5, 120)
    )
 
    forAll (factorials) { (n: Int, factorial: Int) =>
      whenever (n >= 0) {
        bizarreFactorial(n) should be (factorial)
      }
    }
  }
}

Mr. Marick’s constraints were to use apply, but not to use either iteration or recursion. Scala has apply, but its purpose is to allow you to use an object as if it were a function. Clojure’s apply is effectively used more like the way Scala uses reduce on collections. Consequently, I could have implemented bizarreFactorial this way:

object Chapter01 {
  def bizarreFactorial(n: Int): Int = n match {
    case x if x < 0 => throw new IllegalArgumentException("Factorial only works for positive integers")
    case 0 => 1
    case _ => 1 to n reduce (_ * _)
  }
}

But Scala has a shorthand for that: product (like sum in Exercise 3 above), which yields slightly more readable code.

object Chapter01 {
  def bizarreFactorial(n: Int): Int = n match {
    case x if x < 0 => throw new IllegalArgumentException("Factorial only works for positive integers")
    case 0 => 1
    case _ => 1 to n product
  }
}

Exercise 5: Other Functions

As this exercise required the demonstration of a handful of functions that Clojure already has defined, I was able to use the Scala analogues in most cases:

class OtherFunctionsSpec extends UnitSpec {
  "Exercise 5a: take" should "create a new sequence of the first n elements of an existing sequence" in {
    1 to 10 take 3 should be (List(1, 2, 3))
  }
 
  "Exercise 5b: distinct" should "remove duplicates from an existing sequence" in {
    val dupes = Seq(1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6)
    dupes.distinct should be (1 to 6)
  }
 
  "Exercise 5c: ++" should "concatenate two sequences together" in {
    val a = 1 to 3
    val b = 4 to 6
    a ++ b should be (1 to 6)
  }
 
  "Exercise 5d: fill" should "create a sequence containing n copies of the same value" in {
    Seq.fill(5)(2) should be (Seq(2, 2, 2, 2, 2))
  }
 
  "Exercise 5e: interleave" should "interleave the elements of two sequences together" in {
    val evens = 0 to 8 by 2
    val odds = 1 to 9 by 2
    evens interleave odds should be (0 to 9)
  }
 
  "Exercise 5f.i: drop" should "remove the first n items from the sequence" in {
    1 to 10 drop 3 should be (4 to 10)
  }
  "Exercise 5f.ii: dropRight" should "remove the last n items from the sequence" in {
    1 to 10 dropRight 3 should be (1 to 7)
  }
 
  "Exercise 5g: flatten" should "turn a sequence of sequences into a sequence containing all of the values of each subsequence" in {
    Seq(1 to 3, 4 to 6, 7 to 9).flatten should be (1 to 9)
  }
 
  "Exercise 5h: grouped" should "yield an iterator that turns the given sequence into a sequence of subsequences, each n items long" in {
    (1 to 9 grouped 3).toSeq should be (Seq(1 to 3, 4 to 6, 7 to 9))
  }
 
  "Exercise 5i: forall" should "test whether all items in a sequence meet a certain condition" in {
    1 to 9 forall { _ < 10 } should be (true)
  }
 
  "Exercise 5j: filterNot" should "remove items meeting a certain criterion from a given sequence" in {
    1 to 10 filterNot { _ % 3 == 0 } should be (Seq(1, 2, 4, 5, 7, 8, 10))
  }
}

Nevertheless, Clojure has one function interleave that Scala does not have out of the box, so I had to implement it myself as an extension method:

object Chapter01 {
  implicit class Ops[A](val seq: Seq[A]) extends AnyVal {
    def interleave(that: Seq[A]): Seq[A] = {
      (seq, that).zipped flatMap { Seq(_, _) }
    }
  }
}

Exercise 6: prefixOf

class PrefixOfSpec extends UnitSpec {
  "Exercise 6: prefixOf" should "test whether a sequence consists of the first few elements of another sequence" in {
    (1 to 3) prefixOf (1 to 10) should be (true)
  }
}

Scala already has startsWith, but it seemed like cheating to use it to implement prefixOf:

object Chapter01 {
  implicit class Ops[A](val seq: Seq[A]) extends AnyVal {
    def prefixOf(that: Seq[A]): Boolean = {
      that startsWith seq
    }
  }
}

So I used take:

object Chapter01 {
  implicit class Ops[A](val seq: Seq[A]) extends AnyVal {
    def prefixOf(that: Seq[A]): Boolean = {
      (that take seq.length) == seq
    }
  }
}

Exercise 7: tails

I came up with three implementations.

class TailsSpec extends UnitSpec {
  val seq = 1 to 4
  val expected = Seq(1 to 4, 2 to 4, 3 to 4, 4 to 4, 4 until 4)
  "Exercise 7a: tails1" should "return a sequence of successively smaller subsequences of the argument" in {
    seq.tails1 should be (expected)
  }
}

Scala already has an implementation of tails although it returns an iterator instead of a fully constructed sequence. Implementing the version of Mr. Marick’s tails function was no harder than calling toSeq:

object Chapter01 {
  implicit class Ops[A](val seq: Seq[A]) extends AnyVal {
    def tails1: Seq[Seq[A]] = seq.tails.toSeq
  }
}

But again, that seems like cheating, so my second implementation was my own.

class TailsSpec extends UnitSpec {
  val seq = 1 to 4
  val expected = Seq(1 to 4, 2 to 4, 3 to 4, 4 to 4, 4 until 4)
  "Exercise 7b: tails2" should "return a sequence of successively smaller subsequences of the argument" in {
    seq.tails2 should be (expected)
  }
}

The solution that first occurred to me was to use pattern matching and recursion:

object Chapter01 {
  implicit class Ops[A](val seq: Seq[A]) extends AnyVal {
    def tails2: Seq[Seq[A]] = {
      def tailn(s: Seq[A]): Seq[Seq[A]] = s match {
        case Seq() => Seq(s)
        case _ => s +: tailn(s.tail)
      }
      tailn(seq)
    }
  }
}

A perfectly valid implementation, and yet I wanted one more.

class TailsSpec extends UnitSpec {
  val seq = 1 to 4
  val expected = Seq(1 to 4, 2 to 4, 3 to 4, 4 to 4, 4 until 4)
  "Exercise 7c: tails3" should "return a sequence of successively smaller subsequences of the argument" in {
    seq.tails3 should be (expected)
  }
}

I took a peek at Mr. Marick’s Clojure implementation. I wanted to do a Scala version of it:

object Chapter01 {
  implicit class Ops[A](val seq: Seq[A]) extends AnyVal {
    def tails3: Seq[Seq[A]] = {
      val seqs = Seq.fill(seq.length + 1)(seq)
      val nToDrop = 0 to seq.length
      (seqs, nToDrop).zipped map (_ drop _)
    }
  }
}

Well, that’s all for Chapter 1. ~~Look for my take on Chapter 2 to come soon.~~ Chapters 2â€“5 cover embedding an object-oriented language in Clojure. Because Scala is a hybrid functionalâ€“object-oriented language, I didn’t really see the point of doing them in Scala. Therefore the next post will cover chapter 6.