Categories

## Scala Saturday – The map Method

One of the most frequently used operations in functional programming is the map operation. The map operation takes a collection of values, performs some transformation on each element, and creates a new collection containing those new elements. The elements in the new collection can be the same type as the elements in the original collection, or they may be of a different type. It just depends on the transformation.

### Sequential Collections

Let’s look at a couple of examples. First, say that you have a list of integers, and you need the squares of those integers:

You can define the function f to calculate the square of a number. Then you can call the `map` method to apply f to each member in the input list and create a new list containing the squares of the items in the original list. In functional programming parlance, we say that you map f over the list to produce the new list. The code looks like this:

```val f = (n: Int) => n * n
val squares = List(2,4,6,8) map f
// squares: List[Int] = List(4, 16, 36, 64)
```

Of course, you can also define the mapping function inline:

```val squares = List(2,4,6,8) map { n => n * n }
// squares: List[Int] = List(4, 16, 36, 64)
```

Second, suppose you need to compute the length of each string in a list:

Similar to the last example, just define a function to calculate the length of a string, and map it over the list of strings with the `map` method:

```val lengths =
List("five", "six", "pick up", "sticks") map {
_.length
}
// lengths: List[Int] = List(4, 3, 7, 6)
```

Notice two things:

1. In both examples, the output list maintains the order of the elements in the input list. This happens because a list is a sequential collection. The same is also true for an array and a sequence. In contrast, as we will see in a moment, order is not maintained when mapping over a non-sequential collection like a set.
2. Whereas the type of both the input list and the output list is the same in the first example—they both contain integers—in the second example, the type of the elements in the output list (integers) is different from the type of the elements of the input list (strings). This happens frequently in functional programming. It is not uncommon to move a collection of inputs through a series of transformations, changing the type with each transformation.

### Sets

The `Set` class(es) also defines a `map` method. It behaves essentially the same as the `map` methods for lists, arrays, or sequences, but there are some minor differences. Sets are not sequential collections, so the order of their elements is not guaranteed. In other words, if you iterate through the input set and get the elements out in a certain order, after you map over it to get the output set, iterating over the elements of the output set may not yield the same order as the counterpart elements in the input set. Furthermore, by definition, sets cannot contain duplicates. So then, what happens if you map a function over the input set that produces duplicate output values? Let’s see:

```val lengths = Set("four", "five", "six", "seven") map {
_.length
}
// lengths: scala.collection.immutable.Set[Int] = Set(4, 3, 5)
```

That makes sense. Duplicates are dropped. Well, now you know. And knowing is half the battle. (What’s the other half, though? They never did tell us that!)

### Strings

Finally, you can map over strings as well. Mapping over strings operates on each character in the string:

```val allcaps = "sesquipedalian" map { _.toUpper }
// allcaps: String = SESQUIPEDALIAN
```

If you need to transform the characters into values of another type, `map` can take a function that transforms characters into a different type:

```val allcaps = "sesquipedalian".toSeq map { _.toInt }
// allcaps: Seq[Int] = Vector(115, 101, 115, ... )
```
Categories

## Scala Saturday – The flatten Method

### Collections

All of Scala’s collections define a `flatten` method that takes a collection of collections and flattens them. That is, it takes the elements of the nested collections, pulls them out, and puts them all together in a new collection. For sequential collections, such as a list, the new collection maintains the order of the elements in the original collections.

To illustrate, let’s say that the heroes of Icewind Dale have to team up with their roguish nemeses to fight a common enemy:

```val heroes = List("Drizzt", "Bruenor", "Wulfgar", "Catti-brie")
val rogues = List("Jarlaxle", "Artemis")
val teams = List(heroes, rogues)
// teams: List[List[String]] =
//   List(
//     List(Drizzt, Bruenor, Wulfgar, Catti-brie),
//     List(Jarlaxle, Artemis) )
```

So now you have a list of lists. To get your temporary alliance, you call `flatten` on `podcasts`:

```val alliance = teams.flatten
// alliance: List[String] =
//   List(Drizzt, Bruenor, Wulfgar, Catti-brie, Jarlaxle, Artemis)
```

As you can see, `flatten` flattens the nested lists into one long list and preserves the order of the elements as they were in the original nested lists.

### Strings

Hey, strings are collections, too, right? Collections of characters, so if it should ever suit your needs, you can flatten a collection of strings into a collection of characters:

```val atrocious = List(
"super", "cali", "fragi", "listic", "expi", "ali", "docious")
val precocious = atrocious.flatten
// precocious: List[Char] = List(s, u, p, e, r, c, a, l, i, ...
```

Of course, more times than not, you probably want to combine those strings into one long string rather than a sequence of characters. That’s where `mkString` comes in. It concatenates a collection of strings together, delimited by whatever separator you prescribe. (Some languages call this operation “join.”) Like so:

```val delimited = List("lock", "stock", "barrel") mkString ", "
// delimited: String = lock, stock, barrel
```

And if you just want to jam the strings all together with no delimiter, just use an empty string as the delimiter:

```val precocious = atrocious mkString ""
// precocious: String = supercalifragilisticexpialidocious
```
Categories

## Scala Saturday – Infix Notation

I have been using infix notation already in previous Scala Saturday posts, but I decided that it deserves some comment in its own right.

Perhaps you need to do some math with complex numbers, so you whip yourself up a quick `Complex` case class with a `plus` method to perform addition:

```case class Complex(re: Double, im: Double) {
def plus(other: Complex): Complex =
Complex(re + other.re, im + other.im)
}
```

No sweat. Now you can add a couple of complex numbers:

```val a = Complex(2, 5)
val b = Complex(1, -3)
val c = a.plus(b)
// c: Complex = Complex(3.0,2.0)
```

Wouldn’t it be great, though, if we could just write this?

```val c = a plus b
```

### The Fix Is In

If this were Java, we’d be AOL. But good news! Scala allows for infix notation. Martin Odersky in Scala by Example puts it this way:

The binary operation E op E′ is always interpreted as the method call E.op(E′).

In other words, you can write this:

```val x = obj.method(arg)
```

… like this:

```val x = obj method arg
```

So, in fact, the following works like a charm:

```val a = Complex(2, 5)
val b = Complex(1, -3)
val c = a plus b
// c: Complex = Complex(3.0,2.0)
```

That’s why you can create a `Range` this way:

```val r = 1 to 7
// r: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3, 4, 5, 6, 7)
```

The Scala library has defined an extension method `to` for `Int`s that constructs a `Range` from a beginning `Int` to an ending `Int`.

### Smooth Operators

This option of writing method calls in the form of binary operations allows you, as you’ve seen already, to ditch some clutter, but it also lets you write in more expressive mathematical terms when appropriate. We add real numbers and concatenate strings with a `+` sign. Why shouldn’t we do the same with complex numbers?

Now technically speaking, Scala does not provide operator overloading. It does something arguably better: It lets you name a method almost anything you want—a number of mathematical operators included! So then, let’s define a `+` method:

```case class Complex(re: Double, im: Double) {
def plus(other: Complex): Complex =
Complex(re + other.re, im + other.im)
def +(other: Complex) = plus(other)
}
```

Now you could write this:

```val a = Complex(2, 5)
val b = Complex(1, -3)
val c = a.+(b)
// c: Complex = Complex(3.0,2.0)
```

But (in my best Graham Chapman) that’s just silly! The infix option allows you to write an addition operation naturally as you’ve been doing since grade school:

```val c = a + b
// c: Complex = Complex(3.0,2.0)
```

And you can even chain operations:

```val x = Complex(1,1) + Complex(1,2) +
Complex(2,3) + Complex(3,5)
// x: Complex = Complex(7.0,11.0)
```

Without infix notation, you’d be stuck with this:

```val x = Complex(1,1).
plus(Complex(1,2)).
plus(Complex(2,3)).
plus(Complex(3,5))
// x: Complex = Complex(7.0,11.0)
```

… which is not terrible, but isn’t the infix notation a marked improvement?

Again, there’s nothing special about the `+` sign or any other mathematical symbol: It’s just a method. You can chain other methods calls together in an infix fashion, too. Looking at `Range`s one more time, you can create a `Range` with a custom step size by chaining the `to` method with the `by` method:

```val threes = 0 to 20 by 3
// threes: scala.collection.immutable.Range = Range(0, 3, 6, 9, 12, 15, 18)
```

### Parenthetically Speaking

Infix notation also works when a method takes more than one input, but you do have to group the arguments with parentheses:

```// Oops!
val s = "abc" substring 2,3
// error: ';' expected but integer literal found.
//       "abc" substring 2,3
//                        ^

// Ah, this is better
val s = "abc" substring (2,3)
// s: String = c
```

Also if the method takes multiple parameter sets, you can use infix notation for the first argument, but you must wrap that infix expression in parentheses in order to apply the second argument. Take `foldLeft`, for example:

```val f = (1 to 7 foldLeft 5)(_*_)
// f: Int = 25200
```

That’s not bad, but I suppose it’s a matter of preference whether it is any better than the postfix version:

```val f = (1 to 7).foldLeft(5)(_*_)
// f: Int = 25200
```
Categories

## Scala Saturday – The contains and containsSlice Methods

Scala defines the `contains` method on all its collection classes.

### Sets

Let’s say you have a set containing the nicknames of the guys in the band Rush, and you want to see whether a certain person is in the band. Just use `contains`:

```val rush = Set("Dirk", "Lerxst", "Pratt")

val gotAlex = rush contains "Lerxst"
// gotAlex: Boolean = true
val gotAngus = rush contains "Angus"
// gotAngus: Boolean = false
```

### Arrays, Lists, and Vectors (Oh, My!)

`Seq` and the sequence-like classes all define the `contains` method:

```val rushSeq = Seq("Dirk", "Lerxst", "Pratt")
val rushA = Array("Dirk", "Lerxst", "Pratt")
val rushL = List("Dirk", "Lerxst", "Pratt")
val rushV = Vector("Dirk", "Lerxst", "Pratt")

val gotGene = rushSeq contains "Gene"
// gotGene: Boolean = false
val gotNeil = rushA contains "Pratt"
// gotNeil : Boolean = true
val gotAlex = rushL contains "Lerxst"
// gotAlex : Boolean = true
val gotPeter = rushV contains "Peter"
// gotPeter : Boolean = false
```

Sequences and the like also define a `containsSlice` method that takes a sequence and checks it is found in the collection. Order does matter, though:

```val gotGedAndAl = rushSeq containsSlice Seq("Dirk", "Lerxst")
// gotGedAndAl: Boolean = true

// rushSeq has "Dirk" before "Lerxst", so the following fails
val gotAlAndGed = rushSeq containsSlice Seq("Lerxst", "Dirk")
// gotAlAndGed: Boolean = false
```

### Strings

Because Scala just uses Java’s `String` class, we inherit the following from Java:

```val gotX = "Lerxst" contains 'x'
// gotX : Boolean = true
val gotA = "Lerxst" contains 'A'
// gotA : Boolean = false
```

Java overloads `contains` to accept a `String` as well as a `char`:

```val gotXs = "Lerxst" contains "xs"
// gotXs : Boolean = true
val gotAb = "Lerxst" contains "Ab"
// gotAb : Boolean = false
```

Because a `String` is also a sequence, Scala extends `String` with `containsSlice` if you prefer (perhaps for idiomatic reasons) to use it instead of `contains`. It can take a `String` or a sequence of `Char`s:

```val gotXs = "Lerxst" containsSlice "xs"
// gotXs : Boolean = true
val gotXs = "Lerxst" containsSlice Seq('x', 's')
// gotXs : Boolean = true
```

### Maps

`Map` has a `contains` method, and it operates on the `Map`‘s keys, not its values or its key-value pairs:

```val rushM = Map(
"Dirk" -> "bass",
"Lerxst" -> "guitar",
"Pratt" -> "drums")
val gotGed = rushM contains "Dirk"
// val gotGed : bool = true
```

To look among a `Map`‘s values, get the `valuesIterator` first. I’m not wild about this interface. It should have been `values` instead, but `values` returns an `Iterable`, which has no contains method:

```val gotDrummer = rushM.valuesIterator contains "drums"
// gotDrummer: Boolean = true
val gotSitarist = rushM.valuesIterator contains "sitar"
// gotSitarist: Boolean = false
```

There is no `contains` variant that searches on a key-value pair. You can define an extension method `containsPair`:

```object MapExt {
implicit class RichMap[A,B](val m: Map[A,B]) extends AnyVal {
def containsPair(p: (A,B)): Boolean =
m get p._1 contains p._2
}
}

import MapExt._

val gotGedOnBass = rushM containsPair ("Dirk" -> "bass")
// gotGedOnBass: Boolean = true

val gotGedOnFlute = rushM containsPair ("Dirk" -> "flute")
// gotGedOnFlute: Boolean = false

val gotGeorgeOnSitar = rushM containsPair ("George" -> "sitar")
// gotGeorgeOnSitar: Boolean = false
```
Categories

## Scala Saturday — The exists Method

The Scala collections API defines the `exists` method on all its classes. The `exists` method takes a predicate. If any item in the collection meets the predicate, `exists` returns `true`. Otherwise, it returns `false`.

```List(1, 3, 5, 7, 9) exists { _ == 3 }
// res0: Boolean = true

(1 to 12) exists { _ < 1 }
// res1: Boolean = false

Array(1, 3, 5, 7, 9) exists { _ % 3 == 0 }
// res2: Boolean = true

Set(1, 3, 5, 7, 9) exists { _ % 2 == 0 }
// res3: Boolean = false
```

Strings are collections/sequences of characters, so both of the following are valid:

```"asdf" exists { _ == 's' }
// res4: Boolean = true

"asdf" exists { _ == 'b' }
// res5: Boolean = false
```

The `Map` module also defines an `exists` function, but the predicate takes two inputs: one for the key and one for the value.

```val m = Map("A" -> 1, "B" -> 2, "C" -> 4, "D" -> 8)
m exists { _ == "D" -> 8 }
// res6: Boolean = true
```

And of course, if you want to test only the key or only the value, only test the first field or the second field, respectively, of the input tuple.

```m exists { _._1 == "Z" }
// res7: Boolean = false

m exists { _._2 == 2 }
// res8: Boolean = true
```

`Option` also defines an `exists` method. If the option is `Some`, then `exists` applies the predicate to the value in the `Some` instance and returns the result. If the option is `None`, then `exists` always returns `false` (as the REPL is kind enough to point out to us).

```Some("X") exists { _ == "X" }
// res9: Boolean = true

Some("X") exists { _ == "Y" }
// res10: Boolean = false

None exists { _ == "X" }
// <console>:8: warning:
// comparing values of types
// Nothing and String using
// `==' will always yield false
//      None exists { _ == "X" }
//                      ^
// res11: Boolean = false
```
Categories

## FPOO Chapter 6 in Scala

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.

Categories

## 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
}
```

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)
}
it should "return 0 if called on an empty list" in {
val emptyList = List[Int]()
}
}
```

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.

Categories

## Covariant, Contravariant, Contrabass, Codependent

I can never remember Scala‘s notation to indicate a covariant type vs. a contravariant type, so here it is:

### Covariant `[+A]`

`List` can contain an object of type `A` or any subtype of `A`:

``class List[+A]``

### Contravariant `[-A]`

`Function1` accepts as an input an object of type `T1` or any supertype of `T1` (its return type `R`, however, is covariant):

``trait Function1[-T1, +R]``

### Upper Type Bound `[T <: A]`

The following `findSimilar` function (borrowed from this example) accepts an instance of and a `List` of `Similar` objects or of objects that are subtypes of `Similar`:

`def findSimilar[T <: Similar](e: T, xs: List[T]): Boolean`

### Lower Type Bound `[T >: A]`

`Option#orElse` accepts (and returns) an `Option` containing an object of type `A` or any supertype of `A`:

``final def orElse[B >: A](alternative: â‡’ Option[B]): Option[B]``