Foreword

This book is aimed at programmers learning Scala for the first time. We assume you have some familiarity with an object-oriented programming language such as Java, but little or no experience with functional programming.

Our goal is to describe how to use Scala in-the-small. To this end our focus is on the core patterns used in idiomatic Scala code, and we introduce Scala’s features in the context of the patterns they enable. We are not aiming for exhaustive coverage of Scala’s features, and this text is not a reference manual.

Except for a few exercises we don’t rely on any external libraries. You should be able to complete all the problems inside with only a text editor and Scala’s REPL, or an IDE such as the Scala IDE for Eclipse or IntelliJ IDEA.

Essential Scala was created by Noel Welsh and Dave Gurnell of Underscore. It was built using Underscore’s eBook Template, plain text, and a deep and profound love of functional programming.

Conventions Used in This Book

This book contains a lot of technical information and program code. We use the following typographical conventions to reduce ambiguity and highlight important concepts:

Typographical Conventions

New terms and phrases are introduced in italics. After their initial introduction they are written in normal roman font.

Terms from program code, filenames, and file contents, are written in monospace font. Note that we do not distinguish between singular and plural forms. For example, might write String or Strings to refer to the java.util.String class or objects of that type.

References to external resources are written as hyperlinks. References to API documentation are written using a combination of hyperlinks and monospace font, for example: Option.

Source Code

Source code blocks are written as follows. Syntax is highlighted appropriately where applicable:

object MyApp extends App {
  println("Hello world!") // Print a fine message to the user!
}

Some lines of program code are too wide to fit on the page. In these cases we use a continuation character (curly arrow) to indicate that longer code should all be written on one line. For example, the following code:

println("This code should all be written ↩
  on one line.")

should actually be written as follows:

println("This code should all be written on one line.")

Callout Boxes

We use three types of callout box to highlight particular content:

Thanks

Many thanks to Richard Dallway and Jonathan Ferguson, who took on the herculean task of proof reading our early drafts and helped develop the rendering pipeline that produces the finished book.

Thanks also to Danielle Ashley, who updated all of the code samples to use Tut and increased our code quality 100% overnight!

Thanks also to Amir Aryanpour, Audrey Welsh, Daniel Watford, Jason Scott, Joe Halliwell, Jon Pearce, Konstantine Gadyrka, N. Sriram, Rebecca Grenier, and Raffael Dzikowski, who sent us corrections and suggestions while the book was in early access. Knowing that our work was being used made the long haul of writing worthwhile.

1 Getting Started

Throughout this book we will be working with short examples of Scala code. There are two recommended ways of doing this:

1. Using the Scala console (better for people who like command lines)

2. Using Worksheets feature of Scala IDE (better for people who like IDEs)

We’ll walk through the setup for each process here.

1.1 Setting up the Scala Console

Follow the instructions on http://scala-lang.org to set Scala up on your computer. Once Scala is installed, you should be able to run an interactive console by typing scala at your command line prompt. Here’s an example from OS X:

dave@Jade ~> scala
Welcome to Scala version 2.11.4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.7.0_45).
Type in expressions to have them evaluated.
Type :help for more information.

scala>

You can enter individual expressions at the scala> prompt and press Enter to compile and execute them:

scala> "Hello world!"
res0: String = Hello world!

1.1.1 Entering Single-Line Expressions

Let’s try entering a simple expression:

scala> 1 + 2 + 3
res1: Int = 6

When we press Enter, the console responds with three things:

• an identifier res1;
• a type Int;
• a value 6.

As we will see in the next chapter, every expression in Scala has a type and a value. The type is determined at compile time and the value is determined by executing the expression. Both of these are reported here.

The identifier res1 is a convenience provided by the console to allow us to refer to the result of the expression in future expressions. For example, we can multiply our result by two as follows:

scala> res1 * 2
res2: Int = 12

If we enter an expression that doesn’t yield a useful value, the console won’t print anything in response:

scala> println("Hello world!")
Hello world!

Here, the output "Hello world!" is from our println statement—the expression we entered doesn’t actually return a value. The console doesn’t provide output similar to the output we saw above.

1.1.2 Entering Multi-Line Expressions

We can split long expressions across multiple lines quite simply. If we press enter before the end of an expression, the console will print a | character to indicate that we can continue on the next line:

scala> for(i <- 1 to 3) {
     |   println(i)
     | }
1
2
3

Sometimes we want to enter multiple expressions at once. In these cases we can use the :paste command. We simply type :paste, press Enter, and write (or copy-and-paste) our code. When we’re done we press Ctrl+D to compile and execute the code as normal. The console prints output for every expression in one big block at the end of the input:

scala> :paste
// Entering paste mode (ctrl-D to finish)

val x = 1
val y = 2
x + y

// Exiting paste mode, now interpreting.

x: Int = 1
y: Int = 2
res6: Int = 3

If we have Scala code in a file, we can use :paste to paste the contents of the file into the console. This is much more convenient than re-entering expressions in the console. For example, with a file named example.scala containing 1 + 2 + 3 we can use :paste like so:

scala> :paste example.scala
Pasting file example.scala...
res0: Int = 6

1.1.3 Printing the Type of an Expression

One final tip for using the console. Occasionally we want to know the type of an expression without actually running it. To do this we can use the :type command:

scala> :type println("Hello world!")
Unit

Notice that the console doesn’t execute our println statement in this expression. It simply compiles it and prints out its type, which in this case is something called Unit.

Unit is Scala’s equivalent of void from Java and C. Read Chapter 1 to find out more.

1.2 Setting up Scala IDE

Scala IDE is a plugin that adds Scala language support to Eclipse. A complete version of Scala IDE with Eclipse is also available as a standalone bundle from http://scala-ide.org. This is the easiest way to install the software so we recommend you install the standalone bundle for this course.

Go to http://scala-ide.org now, click the Get the Bundle button, and follow the on-screen instructions to download Scala IDE for your operating system:

Once you have downloaded and uncompressed the bundle you should find an application called Eclipse. Launch this. You will be asked to choose a folder for your workspace:

Accept the default location and you will see an empty main Eclipse window:

1.2.1 Creating your First Application

Your Eclipse workspace is two things: a folder containing files and settings, and a main window where you will be doing most of your Scala programming. In your workspace you can find projects for each Scala application you work on.

Let’s create a project for the book exercises now. Select the File menu and choose New > Scala Project:

Enter a Project name of essential-scala and click Finish. The tree view on the left of your workspace should now contain an empty project:

A project is no good without code to run! Let’s create our first simple Scala application - the obligatory Hello World app. Select the File Menu and choose New > Scala Object:

Name your object HelloWorld and click Finish. A new file called HelloWorld.scala should appear in the tree view on the left of the main window. Eclipse should open the new file in the main editor ready for you to start coding:

The content of the file should read as follows:

object HelloWorld {

}

Replace this text with the following minimalist application:

object HelloWorld {
  def main(args: Array[String]): Unit = {
    println("Hello world!")
  }
}

Select the Run Menu and choose Run. This should execute the code in your application, resulting in the words Hello world! appearing in the Console pane at the bottom of the window. Congratulations - you just ran your first Scala application!

Developers with Java experience will notice the resemblance of the code above to the Java hello world app:

public class HelloWorld {
  public static void main(String[] args) {
    System.out.println("Hello world!");
  }
}

The resemblance is, of course, no coincidence. These two applications compile to more or less the same bytecode and have exactly the same semantics. We will learn much more about the similarities and differences between Scala and Java as the course continues.

1.2.2 Creating your First Worksheet

Compiling and running code whenever you make a change is a time consuming process that isn’t particularly suitable to a learning environment.

Fortunately, Scala IDE allows us to create special files called Scala Worksheets that are specifically designed for training and experimentation. Every time you save a Worksheet, Eclipse automatically compiles and runs your code and displays the output on the right-hand side of your editor. This provides instant feedback, which is exactly what we need when investigating new concepts!

Create your first Scala Worksheet by selecting the File Menu and choosing New > Scala Worksheet:

Enter a Worksheet name of FirstSteps and click Finish. A new file called FirstSteps.sc should appear in the tree view on the left of the main window, and should open it in the main editor in the middle:

Note that the object on the left contains a single line of Scala code:

println("Welcome to the Scala worksheet")

for which Eclipse is displaying the corresponding output on the right:

Welcome to the Scala worksheet

Any expression you add to the left of the editor is evaluated and printed on the right. To demonstrate this, change the text in the editor to the following:

object FirstSteps {
  println("Welcome to the Scala worksheet")

  1 + 1

  if(20 > 10) "left" else "right"

  println("The ultimate answer is " + 42)
}

Save your work by selecting the File Menu and choosing Save (or better still by pressing Ctrl+S). Eclipse should automatically evaluate each line of code and print the results on the right of the editor:

object FirstSteps {
  println("Welcome to the Scala worksheet")   //> Welcome to the Scala worksheet

  1 + 1                                       //> res0: Int(2) = 2

  if(20 > 10) "left" else "right"             //> res1: String = left

  println("The ultimate answer is " + 42)     //> The ultimate answer is 42
}

We’ll dive into what all of the text on the right means as we proceed with the course ahead. For now you’re all set to start honing your Scala skills!

2 Expressions, Types, and Values

In this chapter we look at the fundamental building blocks of Scala programs: expressions, types, and values. Understanding these concepts is necessary to build a mental model of how Scala programs work.

2.1 Your First Program

In the Scala console or worksheet enter "Hello world!" and press return (in the console) or save the worksheet. You should see an interaction similar to this:

"Hello world!"
// res0: String = Hello world!

There is a lot to say about this program. It consists of a single expression, and in particular a literal expression or literal for short.

Scala runs, or evaluates, our program. When we evaluate a program in the Scala console or worksheet we are told two pieces of information: the type of the program, and the value it evaluates to. In this case the type is String and the value is "Hello world!".

Although the output value “Hello world!” looks the same as the program that created it, there is a difference between the two. The literal expression is the program text we entered, while what the console prints is the result of evaluating that program. (Literals are so-named because they literally look like what they evaluate to.)

Let’s look at a slightly more complex program

"Hello world!".toUpperCase
// res1: String = HELLO WORLD!

This program extends our first example by adding a method call. Evaluation in Scala proceeds left to right. First the literal "Hello world!" is evaluated, as in the first example. Then the method toUpperCase is called on the result. This method transforms a string value to its upper case equivalent and returns this new string. This is the final value we see printed by the console.

Once again the type of this program is String, but in this case it evaluates to "HELLO WORLD!"

2.1.1 Compile-time and Run-time

There are two distinct stages that a Scala program goes through: first it is compiled, and if it compiles successfully it can then be run or evaluated. We refer to the first stage as compile-time and the latter as run-time.

When using the Scala console our programs are evaluated as soon as they compile, which gives the appearance that there is only one stage. It is important to understand that compile- and run-time really are distinct, as it is this distinction that allows us to properly understand the difference between types and values.

Compilation is a process of checking that a program makes sense. There are two ways in which a program must “make sense”:

1. It must be syntactically correct, meaning the parts of the program must be arranged according to the grammar of the language. An example English sentence that is not syntactically correct is “on cat mat sat the”. An example syntactically incorrect Scala program is

toUpperCase."Hello world!"
// <console>:2: error: identifier expected but string literal found.
// toUpperCase."Hello world!"
//             ^

2. It must type check, meaning it must obey certain constraints on what a sensible program is. An example English sentence that is syntactically correct but fails to make sense is “the mat sat on the cat”. A simple program that would fail to type check is trying to convert a number to uppercase.

2.toUpperCase
// <console>:13: error: value toUpperCase is not a member of Int
//        2.toUpperCase
//          ^

The concept of upper and lowercase doesn’t make sense for numbers, and the type system will catch this error.

If a program passes the checks at compile-time it may then be run. This is the process of the computer performing the instructions in the program.

Even though a program successfully compiles it can still fail at run-time. Dividing an integer by zero causes a run-time error in Scala.

2 / 0
// java.lang.ArithmeticException: / by zero
//   ... 362 elided

The type of integers, Int, allows division so the program type checks. At run-time the program fails because there is no Int that can represent the result of the division.

2.1.2 Expressions, Types, and Values

So what exactly are expressions, types, and values?

Expressions are part of a program’s text—what we type into a file, or the console or worksheet. They are the main components of a Scala program. We will see other components, namely definitions and statements, in due course. Expressions exist at compile-time.

The defining characteristic of an expression is that it evaluates to a value. A value is information stored in the computer’s memory. It exists at run-time. For example, the expression 2 evaluates to a particular sequence of bits in a particular location in the computer’s memory.

We compute with values. They are entities that our programs can pass around and manipulate. For example, to compute the minimum of two numbers we might write a program like

2.min(3)
// res4: Int = 2

Here we have two values, 2 and 3, and we combine them into a larger program that evaluates to 2.

In Scala all values are objects, which has a particular meaning we will see shortly.

Now let’s turn to types. Types are restrictions on our programs that limit how we can manipulate objects. We have already seen two types, String and Int, and seen that we can perform different operations depending on the type.

At this stage, the most important point about types is that expressions have types but values do not. We cannot inspect an arbitrary piece of the computer’s memory and divine how to interpret it without knowing the program that created it. For example, in Scala the Int and Float types are both represented by 32-bits of memory. There are no tags or other indications that a given 32-bits should be interpreted as an Int or a Float.

We can show that types exist at compile-time by asking the Scala console to tell us the type of an expression that causes a run-time error.

:type 2 / 0
// Int

2 / 0
// java.lang.ArithmeticException: / by zero
//   ... 506 elided

We see that the expression 2 / 0 has type Int even though this expression fails when we evaluate it.

Types, which exist at compile-time, restrict us to writing programs that give a consistent interpretation to values. We cannot claim that a particular 32-bits is at one point an Int and another a Float. When a program type checks, Scala guarantees that all values are used consistently and thus it does not need to record type information in a value’s representation. This process of removing type information is called type erasure¹.

Types necessarily do not contain all possible information about the values that conform to the type. If they did, type checking would be equivalent to running the program. We have already seen that the type system will not prevent us from dividing an Int by zero, which causes a run-time error.

An key part of designing Scala code is deciding which error cases we wish to rule out using the type system. We will see that we can express many useful constraints in the type system, improving the reliability of our programs. We could implement a division operator that used the type system to express the possibility of error, if we decided this was important enough in our program. Using the type system well is one of the main themes of this book.

2.1.3 Take Home Points

We must build a mental model of Scala programs if we are to use Scala. Three fundamental components of this model are expressions, types, and values.

Expressions are the parts of a program that evaluate to a value. They are the major part of a Scala program.

Expressions have types, which express some restrictions on programs. During compile-time the types of our programs are checked. If they are inconsistent then compilation fails and we cannot evaluate, or run, our program.

Values exist in the computer’s memory, and are what a running program manipulates. All values in Scala are objects, the meaning of which we will discuss soon.

2.1.4 Exercises

2.1.4.1 Type and Value

Using the Scala console or worksheet, determine the type and value of the following expressions:

1 + 2

"3".toInt

"foo".toInt

println("foo")
// foo

println("foo".toInt)
// java.lang.NumberFormatException: For input string: "foo"
//   at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
//   at java.lang.Integer.parseInt(Integer.java:580)
//   at java.lang.Integer.parseInt(Integer.java:615)
//   at scala.collection.immutable.StringLike$class.toInt(StringLike.scala:272)
//   at scala.collection.immutable.StringOps.toInt(StringOps.scala:29)
//   ... 750 elided

2.2 Interacting with Objects

In the previous section we saw the fundamental components of Scala programs: expressions, types, and values. We learned that all values are objects. In this section we will learn more about objects and how we can interact with them.

2.2.1 Objects

An object is a grouping of data and operations on that data. For example, 2 is an object. The data is the integer 2, and the operations on that data are familiar operations like +, -, and so on.

We have some special terminology for the data and operations of an object. The operations are known as methods. The data is stored in fields.

2.2.2 Method Calls

We interact with objects by calling methods². We have already seen some examples of calling methods. For example, we have seen we can get the uppercase version of a String by calling its toUpperCase method.

"hello".toUpperCase
// res0: String = HELLO

Some methods accept parameters or arguments, which control how the method works. The take method, for example, takes characters from a String. We must pass a parameter to take to specify how many characters we want.

"abcdef".take(3)
// res1: String = abc

"abcdef".take(2)
// res2: String = ab

anExpression.methodName(param1, ...)

anExpression.methodName

A method call is an expression, and thus evaluates to an object. This means we can chain method calls together to make more complex programs:

"hello".toUpperCase.toLowerCase
// res3: String = hello

In what order are the various expressions in a method call evaluated? Method parameters are evaluated left-to-right, before the method is called. So in the expression

"Hello world!".take(2 + 3)
// res4: String = Hello

the expression "Hello world!" is evaluated first, then 2 + 3 (which requires evaluating 2 and then 3 first), then finally "Hello world!".take(5).

2.2.3 Operators

Because every value in Scala is an object we can also call methods on primitive types such as Int and Boolean. This is in contrast to Java where int and boolean are not objects:

123.toShort // this is how we define a `Short` in Scala
// res5: Short = 123

123.toByte // this is how we define a `Byte`
// res6: Byte = 123

But if an Int is an object, what are the basic mathematical operators such as + and -? Are they also methods? Yes—Scala methods can have symbolic names as well as alphanumeric ones!

43 - 3 + 2
// res7: Int = 42

43.-(3).+(2)
// res8: Int = 42

(Note that in Scala 2.10 and earlier you would have to write (43).-(3).+(2) to prevent 43. being interpreted as a Double.)

We can use infix operator notation with any method that takes one parameter, regardless of whether it has a symbolic or alphanumeric name:

"the quick brown fox" split " "
// res: Array[String] = Array(the, quick, brown, fox)

Infix notation is one of several syntactic shorthands that allow us to write simple operator expressions instead of verbose method calls. There are also notations for prefix, postfix, right-associative, and assignment-style operators, but there are much less common than infix notation.

A question poses itself—what precedence rules should we associate with infix operators? Scala uses a set of precedence rules derived from the identifiers we use as method names that follow our intuitive understanding from mathematics and logic:

2 * 3 + 4 * 5
// res11: Int = 26

(2 * 3) + (4 * 5)
// res12: Int = 26

2 * (3 + 4) * 5
// res13: Int = 70

2.2.4 Take home points

All Scala values are objects. We interact with objects by calling methods on them. If you come from a Java background note we can call methods on Int or any other primitive value.

The syntax for a method call is

anExpression.methodName(parameter, ...)

or

anExpression methodName parameter

Scala has very few operators - almost everything is a method call. We use syntactic conventions like infix operator notation to keep our code simple and readable, but we can always fall back to standard method notation where it makes sense.

As we will see, Scala’s focus on programming with expressions allows us to write much shorter code than we can in Java. It also allows us to reason about code in a very intuitive way using values and types.

2.2.5 Exercises

2.2.5.1 Operator Style

Rewrite in operator-style

"foo".take(1)
// res14: String = f

"foo" take 1
// res15: String = f

Rewrite in method call style

1 + 2 + 3
// res16: Int = 6

1.+(2).+(3)
// res17: Int = 6

2.2.5.2 Substitution

What is the difference between the following expressions? What are the similarities?

1 + 2 + 3

6

2.3 Literal Objects

We have already covered some of Scala’s basic types. In this section we’re going to round out that knowledge by covering all of Scala’s literal expressions. A literal expression represents a fixed value that stands “for itself”. Here’s an example:

42
// res0: Int = 42

This interaction at the REPL shows us that the literal 42 evaluates to the Int 42.

Don’t confuse a literal with the value it evaluates to! The literal expression is the representation in the program text before the program is run, and the value is the representation in the computer’s memory after the program has run.

If you have prior programming experience, particularly Java experience, the literals in Scala should be familiar to you.

2.3.1 Numbers

Numbers share the same types available in Java: Int for 32-bit integers, Double for 64-bit floating point, Float for 32-bit floating point, and Long for 64-bit integers.

42
// res1: Int = 42

42.0
// res2: Double = 42.0

42.0f
// res3: Float = 42.0

42L
// res4: Long = 42

Scala also has 16-bit Short integers and 8-bit Bytes, but there is no literal syntax for creating them. Instead, we create them using methods called toShort and toByte.

2.3.2 Booleans

Booleans are exactly the same as Java: true or false.

true
// res5: Boolean = true

false
// res6: Boolean = false

2.3.3 Characters

Chars are 16-bit Unicode values written as a single character enclosed in single quotes.

'a'
// res7: Char = a

2.3.4 Strings

Strings are exactly Java’s strings, and are written the same way.

"this is a string"
// res8: String = this is a string

"the\nusual\tescape characters apply"
// res9: String =
// the
// usual    escape characters apply

2.3.5 Null

Null is the same as Java, though not used nearly as often. Scala’s null also has its own type: Null.

null
// res10: Null = null

2.3.6 Unit

Unit, written (), is the Scala equivalent of Java’s void. Unit is the result of expressions that evaluate to no interesting value, such as printing to standard output using println. The console doesn’t print unit but we can ask for the type of an expression to see that unit is in fact the result of some expressions.

()

:type ()
// Unit

println("something")
// something

:type println("something")
// Unit

Unit is an important concept in Scala. Many of Scala’s syntactic constructs are expressions that have types and values. We need a placeholder for expressions that don’t yield a useful value, and unit provides just that.

2.3.7 Take home points

In this section we have seen literal expressions, which evaluate to basic data types. These basics types are mostly identical to Java, except for Unit which has no equivalent.

We note that every literal expression has a type, and evaluates to a value—something which is also true for more complex Scala expressions.

In the next section we will learn how to define our own object literals.

2.3.8 Exercises

2.3.8.1 Literally Just Literals

What are the values and types of the following Scala literals?

42

true

123L

42.0

2.3.8.2 Quotes and Misquotes

What is the difference between the following literals? What is the type and value of each?

'a'

"a"

2.3.8.3 An Aside on Side-Effects

What is the difference between the following expressions? What is the type and value of each?

"Hello world!"

println("Hello world!")

2.3.8.4 Learning By Mistakes

What is the type and value of the following literal? Try writing it on the REPL or in a Scala worksheet and see what happens!

'Hello world!'

2.4 Object Literals

So far we’ve seen how to create objects of built-in types like Int and String and combine them into expressions. In this section we will see how to create objects of our own design using object literals.

When we write an object literal we use a declaration, which is a different kind of program to an expression. A declaration does not evaluate to a value. Instead it associates a name with a value. This name can then be used to refer to the value in other code.

We can declare an empty object as follows:

object Test {}

This is not an expression—it does not evaluate to a value. Rather, it binds a name (Test) to a value (an empty object).

Once we have bound the name Test we can use it in expressions, where it evaluates to the object we have declared. The simplest expression is just the name on its own, which evaluates to the value itself:

Test
// res0: Test.type = Test$@779732fb

This expression is equivalent to writing a literal like 123 or "abc". Note that the type of the object is reported as Test.type. This is not like any type we’ve seen before—it’s a new type, created just for our object, called a singleton type. We cannot create other values of this type.

Empty objects are not so useful. Within the body (between the braces) of an object declaration we can put expressions. It is more common, however, to put declarations such as declaring methods, fields, or even more objects.

object name {
  declarationOrExpression ...
}

Let’s see how to declare methods and fields.

2.4.1 Methods

We interact with objects via methods so let’s create an object with a method.

object Test2 {
  def name: String = "Probably the best object ever"
}

Here we’ve create a method called name. We can call it in the usual way.

Test2.name
// res1: String = Probably the best object ever

Here’s an object with a more complex method:

object Test3 {
  def hello(name: String) =
    "Hello " + name
}

Test3.hello("Noel")
// res2: String = Hello Noel

def name(parameter: type, ...): resultType =
  bodyExpression

def name: resultType =
  bodyExpression

2.4.2 Fields

An object can also contain other objects, called fields. We introduce these using the keywords val or var, which look similar to def:

object Test4 {
  val name = "Noel"
  def hello(other: String): String =
    name + " says hi to " + other
}

Test4.hello("Dave")
// res3: String = Noel says hi to Dave

val name: type = valueExpression

var name: type = valueExpression

Using val defines an immutable field, meaning we cannot change the value bound to the name. A var field is mutable, allowing us to change the bound value.

Always prefer val to var. Scala programmers prefer to use immutable fields wherever possible, as this maintains substitution. While you will no doubt create the occasional mutable field in your application code, we will stay away from var for most of this course and you should do the same in your Scala programming.

2.4.3 Methods versus fields

You might wonder why we need fields when we can have methods of no arguments that seem to work the same. The difference is subtle—a field gives a name to a value, whereas a method gives a name to a computation that produces a value.

Here’s an object that shows the difference:

object Test7 {
   val simpleField = {
     println("Evaluating simpleField")
     42
   }
   def noParameterMethod = {
     println("Evaluating noParameterMethod")
     42
   }
}

Here we have used a println expression to print something to the console, and a block expression (expressions surrounded by { and }) to group expressions. We’ll see more about block expressions in the next section.

Notice how the console says we’ve defined an object, but it hasn’t run either of our println statements? This is due to a quirk of Scala and Java called lazy loading.

Objects and classes (which we’ll see later) aren’t loaded until they are referenced by other code. This is what prevents Scala loading the entire standard library into memory to run a simple "Hello world!" app.

Let’s force Scala to evaluate our object body by referencing Test7 in an expression:

Test7
// Evaluating simpleField
// res4: Test7.type = Test7$@da0141b

When the object is first loaded, Scala runs through its definitions and calculates the values of each of its fields. This results in the code printing "Evaluating simpleField" as a side-effect.

The body expression of a field is run only once after which the final value is stored in the object. The expression is never evaluated again—notice the lack of println output below.

Test7.simpleField
// res5: Int = 42

Test7.simpleField
// res6: Int = 42

The body of a method, on the other hand, is evaluated every time we call the method—notice the repeated println output below.

Test7.noParameterMethod
// Evaluating noParameterMethod
// res7: Int = 42

Test7.noParameterMethod
// Evaluating noParameterMethod
// res8: Int = 42

2.4.4 Take home points

In this section we have created our own objects, given them methods and fields, and referenced them in expressions.

We have seen the syntax for declaring objects

object name {
  declarationOrExpression ...
}

for declaring methods

def name(parameter: type, ...): resultType = bodyExpression

and for declaring fields

val name = valueExpression
var name = valueExpression

All of these are declarations, binding names to values. Declarations are different to expressions. They do not evaluate to a value and do not have a type.

We have also seen the difference between methods and fields—fields refer to values stored within an object, whereas methods refer to computations that produce values.

2.4.5 Exercises

2.4.5.1 Cat-o-matique

The table below shows the names, colour, and favourite foods of three cats. Define an object for each cat. (For experienced programmers: we haven’t covered classes yet.)

object Oswald {
  val colour: String = "Black"
  val food: String = "Milk"
}

object Henderson {
  val colour: String = "Ginger"
  val food: String = "Chips"
}

object Quentin {
  val colour: String = "Tabby and white"
  val food: String = "Curry"
}

2.4.5.2 Square Dance!

Define an object called calc with a method square that accepts a Double as an argument and… you guessed it… squares its input. Add a method called cube that cubes its input calling square as part of its result calculation.

object calc {
  def square(x: Double) = x * x
  def cube(x: Double) = x * square(x)
}

2.4.5.3 Precise Square Dance!

Copy and paste calc from the previous exercise to create a calc2 that is generalized to work with Ints as well as Doubles. If you have Java experience, this should be fairly straightforward. If not, read the solution below.

object calc2 {
  def square(value: Double) = value * value
  def cube(value: Double) = value * square(value)

  def square(value: Int) = value * value
  def cube(value: Int) = value * square(value)
}

calc2.square(1.0) // calls the `Double` version of `square`
// res11: Double = 1.0

calc2.square(1)   // calls the `Int` version `square`
// res12: Int = 1

val x: Int = calc.square(2) // compile error
// <console>:13: error: type mismatch;
//  found   : Double
//  required: Int
//        val x: Int = calc.square(2) // compile error
//                                ^

val x: Int = calc.square(2).toInt // toInt rounds down
// x: Int = 4

2.4.5.4 Order of evaluation

When entered on the console, what does the following program output, and what is the type and value of the final expression? Think carefully about the types, dependencies, and evaluation behaviour of each field and method.

object argh {
  def a = {
    println("a")
    1
  }

  val b = {
    println("b")
    a + 2
  }

  def c = {
    println("c")
    a
    b + "c"
  }
}

argh.c + argh.b + argh.a

argh.c + argh.b + argh.a
// b
// a
// c
// a
// a
// res13: String = 3c31

- We calculate the main sum at the end of the program, which...
  - Loads `argh`, which...
    - Calculates all the fields in `argh`, which...
      - Calculates `b`, which...
        - Prints `"b"`
        - Evaluates `a + 2`, which...
          - Calls `a`, which...
            - Prints `"a"`
            - Returns `1`
          - Returns `1 + 2`
        - Stores the value `3` in `b`
  - Calls `argh.c`, which...
    - Prints `"c"`
    - Evaluates `a`
      - Prints `"a"`
      - Returns `1` - Which we discard
    - Evaluates `b + "c"`, which...
      - Retrieves the value `3` from `b`
        - Retrieves the value `"c"`
        - Evaluates the `+`, determining that it actually refers to string
          concatenation and converting `3` to `"3"`
        - Returns the `String` `"3c"`
  - Calls `argh.b`, which...
    - Retrieves the value `3` from `b`
  - Evaluates the first `+`, determining that it actually refers to string
    concatentation, and yielding `"3c3"`
  - Calls `argh.a`, which...
    - Prints `"a"`
    - Returns `1`
  - Evaluates the first `+`, determining that it actually refers to string
    concatentation, and yielding `"3c31"`

2.4.5.5 Greetings, human

Define an object called person that contains fields called firstName and lastName. Define a second object called alien containing a method called greet that takes your person as a parameter and returns a greeting using their firstName.

What is the type of the greet method? Can we use this method to greet other objects?

object person {
  val firstName = "Dave"
  val lastName = "Gurnell"
}

object alien {
  def greet(p: person.type) =
    "Greetings, " + p.firstName + " " + p.lastName
}

alien.greet(person)
// res15: String = Greetings, Dave Gurnell

2.4.5.6 The Value of Methods

Are methods values? Are they expressions? Why might this be the case?

object calculator {
  def square(x: Int) = x * x
}

val someField = calculator.square
// <console>:15: error: missing argument list for method square in object calculator
// Unapplied methods are only converted to functions when a function type is expected.
// You can make this conversion explicit by writing `square _` or `square(_)` instead of `square`.
//        val someField = calculator.square
//                                   ^

val someField = calculator.square(2)
// someField: Int = 4

object clock {
  def time = System.currentTimeMillis
}

val now = clock.time
// now: Long = 1594032605030

val aBitLaterThanNow = clock.time
// aBitLaterThanNow: Long = 1594032605068

2.5 Writing Methods

In the previous section we saw the syntax of methods. One of our main goals in this course is to go beyond syntax and give you systematic methods for constructing Scala programs. This is our first section dealing with such matters. In this section we’re going to look at a systematic method for constructing methods. As you gain experience with Scala you can drop some of the steps of this method, but we strongly suggest you follow this method during the course.

To make the advice concrete we’ll use this exercise from the previous section as an example:

Define an object called calc with a method square that accepts a Double as an argument and… you guessed it… squares its input. Add a method called cube that cubes its input, calling square as part of its result calculation.

2.5.1 Identify the Input and Output

Your first step is to identify the types of the input parameters, if any, and the result of the method.

In many cases the exercises will tell you the types and you can just read them straight from the description. In the example above the input type is given as Double. The result type we can infer is also Double.

2.5.2 Prepare Test Cases

Types alone don’t tell all the story. There are many Double to Double functions, but few that implement squaring. Thus we should prepare some test cases that illustrate the expected behaviour of the method.

We’re not going to use a testing library in this course, as we’re trying to avoid external dependencies. We can implement a poor-man’s testing library using the assert function that Scala provides. For our square example we might have test cases like

assert(square(2.0) == 4.0)
assert(square(3.0) == 9.0)
assert(square(-2.0) == 4.0)

2.5.3 Write the Declaration

With types and test cases ready we can now write the method declaration. We haven’t developed the body yet so use ???, another nifty Scala feature, in its place.

def square(in: Double): Double =
  ???

This step should be mechanical given the information gathered in the previous steps.

2.5.4 Run the Code

Run the code and check it compiles (and thus we haven’t made any typos) and also that our tests fail (and thus are testing something). You may need to place the tests after the method declaration.

2.5.5 Write the Body

We’re now ready to write the body of our method. We will develop a number of techniques for this throughout the course. For now, we’re going to look at two techniques.

2.5.5.1 Consider the Result Type

The first technique is to look at the result type, in this case Double. How can we create Double values? We could write a literal, but that obviously won’t be correct in this case. The other way we know to create a Double is to call a method on some object, which brings us to the next technique.

2.5.5.2 Consider the Input Type

Our next technique is to look at the type of input parameters to the method. In this case we have a Double. We have established we need to create a Double, so what methods can we call to create a Double from our input? There are many such methods, and here we have to use our domain knowledge to select * as the correct method to call.

We can now write our complete method as

def square(in: Double): Double =
  in * in

2.5.6 Run the Code, Again

Finally we should run the code again and check that the tests all pass in this case.

This is very simple example but practicing the process now will serve you well for the more complicated examples we will encounter later.

def name(parameter: type, ...): resultType =
 ???

2.6 Compound Expressions

We have almost finished our basic introduction to Scala. In this section we are going to look at two special kinds of expressions, conditionals and blocks, we will need in more complicated programs.

2.6.1 Conditionals

A conditional allows us to choose an expression to evaluate based on some condition. For example, we can choose a string based on which of two numbers is the smallest.

if(1 < 2) "Yes" else "No"
// res0: String = Yes

The expression that is not selected does not get evaluated. This is apparent if we use an expression with a side-effect.

if(1 < 2) println("Yes") else println("No")
// Yes

We can tell the expression println("No") is not evaluated because No is not output to the console.

if(condition)
  trueExpression
else
  falseExpression

2.6.2 Blocks

Blocks are expressions that allow us to sequence computations together. They are written as a pair of braces containing sub-expressions separated by semicolons or newlines.

{ 1; 2; 3 }
// <console>:13: warning: a pure expression does nothing in statement position; you may be omitting necessary parentheses
//        { 1; 2; 3 }
//          ^
// <console>:13: warning: a pure expression does nothing in statement position; you may be omitting necessary parentheses
//        { 1; 2; 3 }
//             ^
// error: No warnings can be incurred under -Xfatal-warnings.

As you can see, executing this code causes the console to raise a number of warnings and return the Int value 3.

A block is a sequence of expressions or declarations surrounded by braces. A block is also an expression: it executes each of its sub-expressions in order and returns the value of the last expression.

Why execute 1 and 2 if we’re going to throw their values away? This is a good question, and is the reason the Scala compiler raised those warnings above.

One reason to use a block is to use code that produces side-effects before calculating a final value:

{
  println("This is a side-effect")
  println("This is a side-effect as well")
  3
}
// This is a side-effect
// This is a side-effect as well
// res3: Int = 3

We can also use a block when we want to name intermediate results, such as

def name: String = {
  val title = "Professor"
  val name = "Funkenstein"
  title + " " + name
}

name
// res4: String = Professor Funkenstein

{
   declarationOrExpression ...
   expression
}

2.6.3 Take home points

Conditional expressions allow us to choose an expression to evaluate based on a Boolean condition. The syntax is

if(condition)
  trueExpression
else
  falseExpression

A conditional, being an expression, has a type and evaluates to an object.

A block allows us to sequence expressions and declarations. It is commonly used when we want to sequence expressions with side-effects, or name intermediate results in a computation. The syntax is

{
   declarationOrExpression ...
   expression
}

The type and value of a block is that of the last expression in the block.

2.6.4 Exercises

2.6.4.1 A Classic Rivalry

What is the type and value of the following conditional?

if(1 > 2) "alien" else "predator"

if(1 > 2) "alien" else "predator"
// res6: String = predator

2.6.4.2 A Less Well Known Rivalry

What about this conditional?

if(1 > 2) "alien" else 2001

if(1 > 2) "alien" else 2001
// res8: Any = 2001

2.6.4.3 An if Without an else

What about this conditional?

if(false) "hello"

if(false) "hello"
// res10: Any = ()

2.7 Conclusion

We have had a very brief introduction to the fundamentals of Scala:

• expressions, which evaluate to values; and
• declarations, which gives names to values.

We’ve seen how we can write literals for many objects, and use method calls and compound expressions to create new objects from existing ones.

We have also declared our own objects, and constructed methods and fields.

Next we’re going to see how a new kind of declaration, a class, provides a template for creating objects. Classes allow us to reuse code and unify similar objects with a common type.

3 Objects and Classes

In the previous chapter we saw how to create objects and interact with them via method calls. In this section we’re going to see how we can abstract over objects using classes. Classes are a template for constructing objects. Given a class we can make many objects that have the same type and share common properties.

3.1 Classes

A class is a template for creating objects that have similar methods and fields. In Scala a class also defines a type, and objects created from a class all share the same type. This allows us to overcome the problem we had in the Greetings, Human exercise in the last chapter.

3.1.1 Defining a Class

Here is a declaration for a simple Person class:

class Person {
  val firstName = "Noel"
  val lastName = "Welsh"
  def name = firstName + " " + lastName
}

Like an object declaration, a class declaration binds a name (in this case Person) and is not an expression. However, unlike an object name, we cannot use a class name in an expression. A class is not a value, and there is a different namespace in which classes live.

Person
// <console>:13: error: not found: value Person
//        Person
//        ^

We can create a new Person object using the new operator. Objects are values and we access their methods and fields in the usual way:

val noel = new Person
// noel: Person = Person@3a1d255f

noel.firstName
// res1: String = Noel

Notice the type of the object is Person. The printed value contains a code in the format @xxxxxxxx, which is a unique identifier for that particular object. Each call to new creates a distinct object of the same type:

noel
// res2: Person = Person@3a1d255f

val newNoel = new Person
// newNoel: Person = Person@d31acc3

val anotherNewNoel = new Person
// anotherNewNoel: Person = Person@73b7d0e4

This means we can write a method that takes any Person as a parameter:

object alien {
  def greet(p: Person) =
    "Greetings, " + p.firstName + " " + p.lastName
}

alien.greet(noel)
// res3: String = Greetings, Noel Welsh

alien.greet(newNoel)
// res4: String = Greetings, Noel Welsh

3.1.2 Constructors

As it stands our Person class is rather useless: we can create as many new objects as we want but they all have the same firstName and lastName. What if we want to give each person a different name?

The solution is to introduce a constructor, which allows us to pass parameters to new objects as we create them:

class Person(first: String, last: String) {
  val firstName = first
  val lastName = last
  def name = firstName + " " + lastName
}

val dave = new Person("Dave", "Gurnell")
// dave: Person = Person@24718052

dave.name
// res5: String = Dave Gurnell

The constructor parameters first and last can only be used within the body of the class. We must declare a field or method using val or def to access data from outside the object.

Constructor arguments and fields are often redundant. Fortunately, Scala provides us a useful short-hand way of declaring both in one go. We can prefix constructor parameters with the val keyword to have Scala define fields for them automatically:

class Person(val firstName: String, val lastName: String) {
  def name = firstName + " " + lastName
}

new Person("Dave", "Gurnell").firstName
// res6: String = Dave

val fields are immutable—they are initialized once after which we cannot change their values. Scala also provides the var keyword for defining mutable fields.

Scala programmers tend to prefer to write immutability and side-effect-free code so we can reason about it using the substitution model. In this course we will concentrate almost exclusively on immutable val fields.

class Name(parameter: type, ...) {
  declarationOrExpression ...
}

class Name(val parameter: type, ...) {
  declarationOrExpression ...
}

3.1.3 Default and Keyword Parameters

All Scala methods and constructors support keyword parameters and default parameter values.

When we call a method or constructor, we can use parameter names as keywords to specify the parameters in an arbitrary order:

new Person(lastName = "Last", firstName = "First")
// res7: Person = Person@58a18e0f

This comes in doubly useful when used in combination with default parameter values, defined like this:

def greet(firstName: String = "Some", lastName: String = "Body") =
  "Greetings, " + firstName + " " + lastName + "!"

If a parameter has a default value we can omit it in the method call:

greet("Busy")
// res8: String = Greetings, Busy Body!

Combining keywords with default parameter values let us skip earlier parameters and just provide values for later ones:

greet(lastName = "Dave")
// res9: String = Greetings, Some Dave!

def greet(title: String = "Citizen", firstName: String = "Some", lastName: String = "Body") =
  "Greetings, " + title + " " + firstName + " " + lastName + "!"

greet("Busy") // this is now incorrect
// res10: String = Greetings, Busy Some Body!

greet(firstName = "Busy") // this is still correct
// res11: String = Greetings, Citizen Busy Body!

3.1.4 Scala’s Type Hierarchy

Unlike Java, which separates primitive and object types, everything in Scala is an object. As a result, “primitive” value types like Int and Boolean form part of the same type hierarchy as classes and traits.

Scala has a grand supertype called Any, under which there are two types, AnyVal and AnyRef. AnyVal is the supertype of all value types, which AnyRef is the supertype of all “reference types” or classes. All Scala and Java classes are subtypes of AnyRef⁴.

Some of these types are simply Scala aliases for types that exist in Java: Int is int, Boolean is boolean, and AnyRef is java.lang.Object.

There are two special types at the bottom of the hierarchy. Nothing is the type of throw expressions, and Null is the type of the value null. These special types are subtypes of everything else, which helps us assign types to throw and null while keeping other types in our code sane. The following code illustrates this:

def badness = throw new Exception("Error")
// badness: Nothing

def otherbadness = null
// otherbadness: Null

val bar = if(true) 123 else badness
// bar: Int = 123

val baz = if(false) "it worked" else otherbadness
// baz: String = null

Although the types of badness and res are Nothing and Null respectively, the types of bar and baz are still sensible. This is because Int is the least common supertype of Int and Nothing, and String is the least common supertype of String and Null.

3.1.5 Take Home Points

In this section we learned how to define classes, which allow us to create many objects with the same type. Thus, classes let us abstract across objects that have similar properties.

The properties of the objects of a class take the form of fields and methods. Fields are pre-computed values stored within the object and methods are computations we can call.

The syntax for declaring classes is

class Name(parameter: type, ...) {
  declarationOrExpression ...
}

We create objects from a class by calling the constructor using the keyword new.

We also learned about keyword parameters and default parameters.

Finally we learned about Scala’s type hierarchy, including the overlap with Java’s type hierarchy, the special types Any, AnyRef, AnyVal, Nothing, Null, and Unit, and the fact that Java and Scala classes both occupy the same subtree of the type hierarchy.

3.1.6 Exercises

We now have enough machinery to have some fun playing with classes.

3.1.6.1 Cats, Again

Recall the cats from a previous exercise:

Define a class Cat and then create an object for each cat in the table above.

class Cat(val colour: String, val food: String)

val oswald = new Cat("Black", "Milk")
val henderson = new Cat("Ginger", "Chips")
val quentin = new Cat("Tabby and white", "Curry")

3.1.6.2 Cats on the Prowl

Define an object ChipShop with a method willServe. This method should accept a Cat and return true if the cat’s favourite food is chips, and false otherwise.

object ChipShop {
  def willServe(cat: Cat): Boolean =
    if(cat.food == "Chips")
      true
    else
      false
}

3.1.6.3 Directorial Debut

Write two classes, Director and Film, with fields and methods as follows:

• Director should contain:
  • a field firstName of type String
  • a field lastName of type String
  • a field yearOfBirth of type Int
  • a method called name that accepts no parameters and returns the full name
• Film should contain:
  • a field name of type String
  • a field yearOfRelease of type Int
  • a field imdbRating of type Double
  • a field director of type Director
  • a method directorsAge that returns the age of the director at the time of release
  • a method isDirectedBy that accepts a Director as a parameter and returns a Boolean

Copy-and-paste the following demo data into your code and adjust your constructors so that the code works without modification:

val eastwood          = new Director("Clint", "Eastwood", 1930)
val mcTiernan         = new Director("John", "McTiernan", 1951)
val nolan             = new Director("Christopher", "Nolan", 1970)
val someBody          = new Director("Just", "Some Body", 1990)

val memento           = new Film("Memento", 2000, 8.5, nolan)
val darkKnight        = new Film("Dark Knight", 2008, 9.0, nolan)
val inception         = new Film("Inception", 2010, 8.8, nolan)

val highPlainsDrifter = new Film("High Plains Drifter", 1973, 7.7, eastwood)
val outlawJoseyWales  = new Film("The Outlaw Josey Wales", 1976, 7.9, eastwood)
val unforgiven        = new Film("Unforgiven", 1992, 8.3, eastwood)
val granTorino        = new Film("Gran Torino", 2008, 8.2, eastwood)
val invictus          = new Film("Invictus", 2009, 7.4, eastwood)

val predator          = new Film("Predator", 1987, 7.9, mcTiernan)
val dieHard           = new Film("Die Hard", 1988, 8.3, mcTiernan)
val huntForRedOctober = new Film("The Hunt for Red October", 1990, 7.6, mcTiernan)
val thomasCrownAffair = new Film("The Thomas Crown Affair", 1999, 6.8, mcTiernan)

eastwood.yearOfBirth
// res16: Int = 1930

dieHard.director.name
// res17: String = John McTiernan

invictus.isDirectedBy(nolan)
// res18: Boolean = false

Implement a method of Film called copy. This method should accept the same parameters as the constructor and create a new copy of the film. Give each parameter a default value so you can copy a film changing any subset of its values:

highPlainsDrifter.copy(name = "L'homme des hautes plaines")
// res19: Film = Film(L'homme des hautes plaines,1973,7.7,Director(Clint,Eastwood,1930))

thomasCrownAffair.copy(yearOfRelease = 1968,
  director = new Director("Norman", "Jewison", 1926))
// res20: Film = Film(The Thomas Crown Affair,1968,6.8,Director(Norman,Jewison,1926))

inception.copy().copy().copy()
// res21: Film = Film(Inception,2010,8.8,Director(Christopher,Nolan,1970))

class Director(
  val firstName: String,
  val lastName: String,
  val yearOfBirth: Int) {

  def name: String =
    s"$firstName $lastName"

  def copy(
    firstName: String = this.firstName,
    lastName: String = this.lastName,
    yearOfBirth: Int = this.yearOfBirth): Director =
    new Director(firstName, lastName, yearOfBirth)
}

class Film(
  val name: String,
  val yearOfRelease: Int,
  val imdbRating: Double,
  val director: Director) {

  def directorsAge =
    yearOfRelease - director.yearOfBirth

  def isDirectedBy(director: Director) =
    this.director == director

  def copy(
    name: String = this.name,
    yearOfRelease: Int = this.yearOfRelease,
    imdbRating: Double = this.imdbRating,
    director: Director = this.director): Film =
    new Film(name, yearOfRelease, imdbRating, director)
}

3.1.6.4 A Simple Counter

Implement a Counter class. The constructor should take an Int. The methods inc and dec should increment and decrement the counter respectively returning a new Counter. Here’s an example of the usage:

new Counter(10).inc.dec.inc.inc.count
// res23: Int = 12

class Counter(val count: Int) {
  def dec = new Counter(count - 1)
  def inc = new Counter(count + 1)
}

3.1.6.5 Counting Faster

Augment the Counter from the previous exercise to allow the user can optionally pass an Int parameter to inc and dec. If the parameter is omitted it should default to 1.

class Counter(val count: Int) {
  def dec(amount: Int = 1) = new Counter(count - amount)
  def inc(amount: Int = 1) = new Counter(count + amount)
}

new Counter(10).inc
// <console>:14: error: missing argument list for method inc in class Counter
// Unapplied methods are only converted to functions when a function type is expected.
// You can make this conversion explicit by writing `inc _` or `inc(_)` instead of `inc`.
//        new Counter(10).inc
//                        ^

class Counter(val count: Int) {
  def dec: Counter = dec()
  def inc: Counter = inc()
  def dec(amount: Int = 1): Counter = new Counter(count - amount)
  def inc(amount: Int = 1): Counter = new Counter(count + amount)
}

new Counter(10).inc.inc(10).count
// res25: Int = 21

3.1.6.6 Additional Counting

Here is a simple class called Adder.

class Adder(amount: Int) {
  def add(in: Int) = in + amount
}

Extend Counter to add a method called adjust. This method should accept an Adder and return a new Counter with the result of applying the Adder to the count.

class Counter(val count: Int) {
  def dec = new Counter(count - 1)
  def inc = new Counter(count + 1)
  def adjust(adder: Adder) =
    new Counter(adder.add(count))
}

public class MyActionListener implements ActionListener {
  public void actionPerformed(ActionEvent evt) {
    // Do some computation
  }
}

3.2 Objects as Functions

In the final exercise of the previous section, we defined a class called Adder:

class Adder(amount: Int) {
  def add(in: Int): Int = in + amount
}

In the discussion we described an Adder as an object representing a computation—a bit like having a method that we can pass around as a value.

This is such a powerful concept that Scala has a fully blown set of language features for creating objects that behave like computations. These objects are called functions, and are the basis of functional programming.

3.2.1 The apply method

For now we are going to look at just one of Scala’s features supporting functional programming—function application syntax.

In Scala, by convention, an object can be “called” like a function if it has a method called apply. Naming a method apply affords us a special shortened call syntax: foo.apply(args) becomes foo(args).

For example, let’s rename the add method in Adder to apply:

class Adder(amount: Int) {
  def apply(in: Int): Int = in + amount
}

val add3 = new Adder(3)
// add3: Adder = Adder@4185f338

add3.apply(2)
// res0: Int = 5

add3(4) // shorthand for add3.apply(4)
// res1: Int = 7

With this one simple trick, objects can “look” syntactically like functions. There are lots of things that we can do with objects that we can’t do with methods, including assign them to variables and pass them around as arguments.

3.2.2 Take home points

In this section we looked at function application syntax, which lets us “call” an object as if it is a function.

Function application syntax is available for any object defining an apply method.

With function application syntax, we now have first class values that behave like computations. Unlike methods, objects can be passed around as data. This takes us one step closer towards true functional programming in Scala.

3.2.3 Exercises

3.2.3.1 When is a Function not a Function?

We’ll get a chance to write some code at the end of the next section. For now we should think about an important theoretical question:

How close does function application syntax get us to creating truly reusable objects to do computations for us? What are we missing?

3.3 Companion Objects

Sometimes we want to create a method that logically belongs to a class but is independent of any particular object. In Java we would use a static method for this, but Scala has a simpler solution that we’ve seen already: singleton objects.

One common use case is auxiliary constructors. Although Scala does have syntax that lets us define multiple constructors for a class, Scala programmers almost always prefer to implement additional constructors as apply methods on an object with the same name as the class. We refer to the object as the companion object of the class. For example:

class Timestamp(val seconds: Long)

object Timestamp {
  def apply(hours: Int, minutes: Int, seconds: Int): Timestamp =
    new Timestamp(hours*60*60 + minutes*60 + seconds)
}

Timestamp(1, 1, 1).seconds
// res1: Long = 3661

As we saw earlier, Scala has two namespaces: a space of type names and a space of value names. This separation allows us to name our class and companion object the same thing without conflict.

It is important to note that the companion object is not an instance of the class—it is a singleton object with its own type:

Timestamp // note that the type is `Timestamp.type`, not `Timestamp`
// res2: Timestamp.type = Timestamp$@137bf92e

class Name {
  ...
}

object Name {
  ...
}

3.3.1 Take home points

Companion objects provide us with a means to associate functionality with a class without associating it with any instance of that class. They are commonly used to provide additional constructors.

Companion objects replace Java’s static methods. They provide equivalent functionality and are more flexible.

A companion object has the same name as its associated class. This doesn’t cause a naming conflict because Scala has two namespaces: the namespace of values and the namespace of types.

A companion object must be defined in the same file as the associated class. When typing on the REPL, the class and companion object must be entered in the same block of code using :paste mode.

3.3.2 Exercises

3.3.2.1 Friendly Person Factory

Implement a companion object for Person containing an apply method that accepts a whole name as a single string rather than individual first and last names.

Tip: you can split a String into an Array of components as follows:

val parts = "John Doe".split(" ")
// parts: Array[String] = Array(John, Doe)

parts(0)
// res3: String = John

class Person(val firstName: String, val lastName: String) {
  def name: String =
    s"$firstName $lastName"
}

object Person {
  def apply(name: String): Person = {
    val parts = name.split(" ")
    new Person(parts(0), parts(1))
  }
}

Person.apply("John Doe").firstName // full method call
// res5: String = John

Person("John Doe").firstName // sugared apply syntax
// res6: String = John

3.3.2.2 Extended Body of Work

Write companion objects for Director and Film as follows:

• the Director companion object should contain:
  • an apply method that accepts the same parameters as the constructor of the class and returns a new Director;
  • a method older that accepts two Directors and returns the oldest of the two.
• the Film companion object should contain:
  • an apply method that accepts the same parameters as the constructor of the class and returns a new Film;
  • a method highestRating that accepts two Films and returns the highest imdbRating of the two;
  • a method oldestDirectorAtTheTime that accepts two Films and returns the Director who was oldest at the respective time of filming.

class Director(
  val firstName: String,
  val lastName: String,
  val yearOfBirth: Int) {

  def name: String =
    s"$firstName $lastName"

  def copy(
    firstName: String = this.firstName,
    lastName: String = this.lastName,
    yearOfBirth: Int = this.yearOfBirth) =
    new Director(firstName, lastName, yearOfBirth)
}

object Director {
  def apply(firstName: String, lastName: String, yearOfBirth: Int): Director =
    new Director(firstName, lastName, yearOfBirth)

  def older(director1: Director, director2: Director): Director =
    if (director1.yearOfBirth < director2.yearOfBirth) director1 else director2
}

class Film(
  val name: String,
  val yearOfRelease: Int,
  val imdbRating: Double,
  val director: Director) {

  def directorsAge =
    director.yearOfBirth - yearOfRelease

  def isDirectedBy(director: Director) =
    this.director == director

  def copy(
    name: String = this.name,
    yearOfRelease: Int = this.yearOfRelease,
    imdbRating: Double = this.imdbRating,
    director: Director = this.director) =
    new Film(name, yearOfRelease, imdbRating, director)
}

object Film {
  def apply(
    name: String,
    yearOfRelease: Int,
    imdbRating: Double,
    director: Director): Film =
    new Film(name, yearOfRelease, imdbRating, director)

  def newer(film1: Film, film2: Film): Film =
    if (film1.yearOfRelease < film2.yearOfRelease) film1 else film2

  def highestRating(film1: Film, film2: Film): Double = {
    val rating1 = film1.imdbRating
    val rating2 = film2.imdbRating
    if (rating1 > rating2) rating1 else rating2
  }

  def oldestDirectorAtTheTime(film1: Film, film2: Film): Director =
    if (film1.directorsAge > film2.directorsAge) film1.director else film2.director
}

3.3.2.3 Type or Value?

The similarity in naming of classes and companion objects tends to cause confusion for new Scala developers. When reading a block of code it is important to know which parts refer to a class or type and which parts refer to a singleton object or value.

This is the inspiration for the new hit quiz, Type or Value?, which we will be piloting below. In each case identify whether the word Film refers to the type or value:

val prestige: Film = bestFilmByChristopherNolan()

new Film("Last Action Hero", 1993, mcTiernan)

Film("Last Action Hero", 1993, mcTiernan)

Film.apply("Last Action Hero", 1993, mcTiernan)

Film.newer(highPlainsDrifter, thomasCrownAffair)

Finally a tough one…

Film.type

3.4 Case Classes

Case classes are an exceptionally useful shorthand for defining a class, a companion object, and a lot of sensible defaults in one go. They are ideal for creating lightweight data-holding classes with the minimum of hassle.

Case classes are created simply by prepending a class definition with the keyword case:

case class Person(firstName: String, lastName: String) {
  def name = firstName + " " + lastName
}

Whenever we declare a case class, Scala automatically generates a class and companion object:

val dave = new Person("Dave", "Gurnell") // we have a class
// dave: Person = Person(Dave,Gurnell)

Person // and a companion object too
// res0: Person.type = Person

What’s more, the class and companion are pre-populated with some very useful features.

3.4.1 Features of a case class

1. A field for each constructor argument—we don’t even need to write val in our constructor definition, although there’s no harm in doing so.

dave.firstName
// res1: String = Dave

2. A default toString method that prints a sensible constructor-like representation of the class (no more @ signs and cryptic hex numbers):

dave
// res2: Person = Person(Dave,Gurnell)

3. Sensible equals, and hashCode methods that operate on the field values in the object.

This makes it easy to use case classes with collections like Lists, Sets and Maps. It also means we can compare objects on the basis of their contents rather than their reference identity:

new Person("Noel", "Welsh").equals(new Person("Noel", "Welsh"))
// res3: Boolean = true

new Person("Noel", "Welsh") == new Person("Noel", "Welsh")
// res4: Boolean = true

4. A copy method that creates a new object with the same field values as the current one:

dave.copy()
// res5: Person = Person(Dave,Gurnell)

Note that the copy method creates and returns a new object of the class rather than returning the current one.

The copy method actually accepts optional parameters matching each of the constructor parameters. If a parameter is specified the new object uses that value instead of the existing value from the current object. This is ideal for use with keyword parameters to let us copy an object while changing the values of one or more fields:

dave.copy(firstName = "Dave2")
// res6: Person = Person(Dave2,Gurnell)

dave.copy(lastName = "Gurnell2")
// res7: Person = Person(Dave,Gurnell2)

new Person("Noel", "Welsh") eq (new Person("Noel", "Welsh"))
// res8: Boolean = false

dave eq dave
// res9: Boolean = true

5. Case classes implement two traits: java.io.Serializable and scala.Product. Neither are used directly. The latter provides methods for inspecting the number of fields and the name of the case class.

3.4.2 Features of a case class companion object

The companion object contains an apply method with the same arguments as the class constructor. Scala programmers tend to prefer the apply method over the constructor for the brevity of omitting new, which makes constructors much easier to read inside expressions:

Person("Dave", "Gurnell") == Person("Noel", "Welsh")
// res10: Boolean = false

Person("Dave", "Gurnell") == Person("Dave", "Gurnell")
// res11: Boolean = true

Finally, the companion object also contains code to implement an extractor pattern for use in pattern matching. We’ll see this later this chapter.

case class Name(parameter: type, ...) {
  declarationOrExpression ...
}

3.4.3 Case objects

A final note. If you find yourself defining a case class with no constructor arguments you can instead a define a case object. A case object is defined just like a regular singleton object, but has a more meaningful toString method and extends the Product and Serializable traits:

case object Citizen {
  def firstName = "John"
  def lastName  = "Doe"
  def name = firstName + " " + lastName
}

Citizen.toString
// res12: String = Citizen

3.4.4 Take Home Points

Case classes are the bread and butter of Scala data types. Use them, learn them, love them.

The syntax for declaring a case class is the same as for declaring a class, but with case appended

case class Name(parameter: type, ...) {
  declarationOrExpression ...
}

Case classes have numerous auto-generated methods and features that save typing. We can override this behaviour on a piece-by-piece basis by implementing the relevant methods ourselves.

In Scala 2.10 and earlier we can define case classes containing 0 to 22 fields. In Scala 2.11 we gain the ability to define arbitrarily-sized case classes.

3.4.5 Exercises

3.4.5.1 Case Cats

Recall that a Cat has a String colour and food. Define a case class to represent a Cat.

case class Cat(colour: String, food: String)

3.4.5.2 Roger Ebert Said it Best…

No good movie is too long and no bad movie is short enough.

The same can’t always be said for code, but in this case we can get rid of a lot of boilerplate by converting Director and Film to case classes. Do this conversion and work out what code we can cut.

case class Director(firstName: String, lastName: String, yearOfBirth: Int) {
  def name: String =
    s"$firstName $lastName"
}

object Director {
  def older(director1: Director, director2: Director): Director =
    if (director1.yearOfBirth < director2.yearOfBirth) director1 else director2
}

case class Film(
  name: String,
  yearOfRelease: Int,
  imdbRating: Double,
  director: Director) {

  def directorsAge =
    yearOfRelease - director.yearOfBirth

  def isDirectedBy(director: Director) =
    this.director == director
}

object Film {
  def newer(film1: Film, film2: Film): Film =
    if (film1.yearOfRelease < film2.yearOfRelease) film1 else film2

  def highestRating(film1: Film, film2: Film): Double = {
    val rating1 = film1.imdbRating
    val rating2 = film2.imdbRating
    if (rating1 > rating2) rating1 else rating2
  }

  def oldestDirectorAtTheTime(film1: Film, film2: Film): Director =
    if (film1.directorsAge > film2.directorsAge) film1.director else film2.director
}

3.4.5.3 Case Class Counter

Reimplement Counter as a case class, using copy where appropriate. Additionally initialise count to a default value of 0.

case class Counter(count: Int = 0) {
  def dec = copy(count = count - 1)
  def inc = copy(count = count + 1)
}

Counter(0) // construct objects without `new`
// res16: Counter = Counter(0)

Counter().inc // printout shows the value of `count`
// res17: Counter = Counter(1)

Counter().inc.dec == Counter().dec.inc // semantic equality check
// res18: Boolean = true

3.4.5.4 Application, Application, Application

What happens when we define a companion object for a case class? Let’s see.

Take our Person class from the previous section and turn it into a case class (hint: the code is above). Make sure you still have the companion object with the alternate apply method as well.

case class Person(firstName: String, lastName: String) {
  def name = firstName + " " + lastName
}

object Person {
  def apply(name: String): Person = {
    val parts = name.split(" ")
    apply(parts(0), parts(1))
  }
}

def apply(name: String): Person =
  // etc...

def apply(firstName: String, lastName: String): Person =
  // etc...

3.5 Pattern Matching

Until now we have interacted with objects by calling methods or accessing fields. With case classes we can interact in another way, via pattern matching.

Pattern matching is like an extended if expression that allows us to evaluate an expression depending on the “shape” of the data. Recall the Person case class we’ve seen in previous examples:

case class Person(firstName: String, lastName: String)

Now imagine we wanted to implement a Stormtrooper that is looking for members of the rebellion. We could use pattern matching like this:

object Stormtrooper {
  def inspect(person: Person): String =
    person match {
      case Person("Luke", "Skywalker") => "Stop, rebel scum!"
      case Person("Han", "Solo") => "Stop, rebel scum!"
      case Person(first, last) => s"Move along, $first"
    }
}

Notice the syntax for a pattern (Person("Luke", "Skywalker")) matches the syntax for constructing the object the pattern matches (Person("Luke", "Skywalker")).

Here it is in use:

Stormtrooper.inspect(Person("Noel", "Welsh"))
// res0: String = Move along, Noel

Stormtrooper.inspect(Person("Han", "Solo"))
// res1: String = Stop, rebel scum!

expr0 match {
  case pattern1 => expr1
  case pattern2 => expr2
  ...
}

3.5.1 Pattern Syntax

Scala has an expressive syntax for writing patterns or guards. For case classes the pattern syntax matches the constructor syntax. Take the data

Person("Noel", "Welsh")
// res2: Person = Person(Noel,Welsh)

A pattern to match against the Person type is written

Person(pat0, pat1)

where pat0 and pat1 are patterns to match against the firstName and lastName respectively. There are four possible patterns we could use in place of pat0 or pat1:

1. A name, which matches any value at that position and binds it to the given name. For example, the pattern Person(first, last) binds the name first to the value "Noel", and the name last to the value "Welsh".

2. An underscore (_), which matches any value and ignores it. For example, as Stormtroopers only care about the first name of ordinary citizens we could just write Person(first, _) to avoid binding a name to the value of the lastName.

3. A literal, which successfully matches only the value the literal respresents. So , for example, the pattern Person("Han", "Solo") matches the Person with first name "Han" and last name "Solo".

4. Another case class using the same constructor style syntax.

Note there is a lot more we can do with pattern matching, and pattern matching is actually extensible. We’ll look at these features in a later section.

3.5.2 Take Home Points

Case classes allow a new form of interaction, called pattern matching. Pattern matching allows us to take apart a case class, and evaluate different expressions depending on what the case class contains.

The syntax for pattern matching is

expr0 match {
  case pattern1 => expr1
  case pattern2 => expr2
  ...
}

A pattern can be one of

1. a name, binding any value to that name;
2. an underscore, matching any value and ignoring it;
3. a literal, matching the value the literal denotes; or
4. a constructor-style pattern for a case class.

3.5.3 Exercises

3.5.3.1 Feed the Cats

Define an object ChipShop with a method willServe. This method should accept a Cat and return true if the cat’s favourite food is chips, and false otherwise. Use pattern matching.

case class Cat(name: String, colour: String, food: String)

object ChipShop {
  def willServe(cat: Cat): Boolean =
    cat match {
      case Cat(???, ???, ???) => ???
    }
}

object ChipShop {
  def willServe(cat: Cat): Boolean =
    cat match {
      case Cat(_, _, "Chips") => true
      case Cat(_, _, _) => false
    }
}

3.5.3.2 Get Off My Lawn!

In this exercise we’re going to write a simulator of my Dad, the movie critic. It’s quite simple: any movie directed by Clint Eastwood gets a rating 10.0, any movie directed by John McTiernan gets a 7.0, while any other movie gets a 3.0. Implement an object called Dad with a method rate which accepts a Film and returns a Double. Use pattern matching.

object Dad {
  def rate(film: Film): Double =
    film match {
      case Film(_, _, _, Director("Clint", "Eastwood", _)) => 10.0
      case Film(_, _, _, Director("John", "McTiernan", _)) => 7.0
      case _ => 3.0
    }
}

3.6 Conclusions

In this section we’ve explored classes. We have seen that classes allow us to abstract over objects. That is, to define objects that share properties in common and have a common type.

We also looked at companion objects, which are used in Scala to define auxillary constructors and other utility methods that don’t belong on a class.

Finally, we introduced case classes, which greatly reduce boilerplate code and allow pattern-matching, a new way of interacting with objects, in addition to method calls.

4 Modelling Data with Traits

We looked in depth at classes in the previous chapter. Classes provide us with a way to abstract over objects that have similar properties, allowing us to write code that works with any object in a class.

In this chapter we explore abstraction over classes, allowing us to write code that works with objects of different classes. We achieve this with a mechanism called traits.

This chapter also marks a change in our focus. In previous chapters we have addressed the technical aspects of constructing Scala code. In this chapter we will initially focus on the technical aspects of traits. Our focus will then change to using Scala as a medium to express our thoughts.

We will see how we can mechanically transform a description of data, called an algebraic datatype, into code. Using structural recursion we can mechanically write code that transforms an algebraic datatype.

4.1 Traits

Traits are templates for creating classes, in the same way that classes are templates for creating objects. Traits allow us to express that two or more classes can be considered the same, and thus both implement the same operations. In other words, traits allow us to express that multiple classes share a common super-type (outside of the Any super-type that all classes share).

4.1.1 An Example of Traits

Let’s start with an example of a trait. Imagine we’re modelling visitors to a website. There are two types of visitor: those who have registered on our site and those who are anonymous. We can model this with two classes:

import java.util.Date

case class Anonymous(id: String, createdAt: Date = new Date())

case class User(
  id: String,
  email: String,
  createdAt: Date = new Date()
)

With these class definitions we’re saying that both anonymous and registered visitors have an id and a creation date. But we only know the email address of registered visitors.

There is obvious duplication here, and it would be nice to not have to write the same definitions twice. More important though, is to create some common type for the two kinds of visitors. If they had some type in common (other than AnyRef and Any) we could write methods that worked on any kind of visitor. We can do this with a trait like so:

import java.util.Date

trait Visitor {
  def id: String      // Unique id assigned to each user
  def createdAt: Date // Date this user first visited the site

  // How long has this visitor been around?
  def age: Long = new Date().getTime - createdAt.getTime
}

case class Anonymous(
  id: String,
  createdAt: Date = new Date()
) extends Visitor

case class User(
  id: String,
  email: String,
  createdAt: Date = new Date()
) extends Visitor

Note the two changes:

• we defined the trait Visitor; and
• we declared that Anonymous and User are subtypes of the Visitor trait by using the extends keyword.

The Visitor trait expresses an interface that any subtype must implement: they must implement a String called id and a createdAt Date. Any sub-type of Visitor also automatically has a method age as defined in Visitor.

By defining the Visitor trait we can write methods that work with any subtype of visitor, like so:

def older(v1: Visitor, v2: Visitor): Boolean =
  v1.createdAt.before(v2.createdAt)

older(Anonymous("1"), User("2", "test@example.com"))
// res5: Boolean = true

Here the method older can be called with either an Anonymous or a User as they are both subtypes of Visitor.

trait TraitName {
  declarationOrExpression ...
}

class Name(...) extends TraitName {
  ...
}

case class Name(...) extends TraitName {
 ...
}

4.1.2 Traits Compared to Classes

Like a class, a trait is a named set of field and method definitions. However, it differs from a class in a few important ways:

• A trait cannot have a constructor—we can’t create objects directly from a trait. Instead we can use a trait to create a class, and then create objects from that class. We can base as many classes as we like on a trait.

• Traits can define abstract methods that have names and type signatures but no implementation. We saw this in the Visitor trait. We must specify the implementation when we create a class that extends the trait, but until that point we’re free to leave definitions abstract.

Let’s return to the Visitor trait to further explore abstract definitions. Recall the definition of Visitor is

import java.util.Date

trait Visitor {
  def id: String      // Unique id assigned to each user
  def createdAt: Date // Date this user first visited the site

  // How long has this visitor been around?
  def age: Long = new Date().getTime - createdAt.getTime
}

Visitor prescribes two abstract methods. That is, methods which do not have an implementation but must be implemented by extending classes. These are id and createdAt. It also defines a concrete method, age, that is defined in terms of one of the abstract methods.

Visitor is used as a building block for two classes: Anonymous and User. Each class extends Visitor, meaning it inherits all of its fields and methods:

val anon = Anonymous("anon1")
// anon: Anonymous = Anonymous(anon1,Mon Jul 06 10:51:40 UTC 2020)

anon.createdAt
// res7: java.util.Date = Mon Jul 06 10:51:40 UTC 2020

anon.age
// res8: Long = 65

id and createdAt are abstract so they must be defined in extending classes. Our classes implement them as vals rather than defs. This is legal in Scala, which sees def as a more general version of val⁶. It is good practice to never define vals in a trait, but rather to use def. A concrete implementation can then implement it using using a def or val as appropriate.

4.1.3 Take Home Points

Traits are a way of abstracting over classes that have similar properties, just like classes are a way of abstracting over objects.

Using a traits has two parts. Declaring the trait

trait TraitName {
  declarationOrExpression ...
}

and extending the trait from a class (usually a case class)

case class Name(...) extends TraitName {
  ...
}

4.1.4 Exercises

4.1.4.1 Cats, and More Cats

Demand for Cat Simulator 1.0 is exploding! For v2 we’re going to go beyond the domestic cat to model Tigers, Lions, and Panthers in addition to the Cat. Define a trait Feline and then define all the different species as subtypes of Feline. To make things interesting, define:

• on Feline a colour as before;
• on Feline a String sound, which for a cat is "meow" and is "roar" for all other felines;
• only Cat has a favourite food; and
• Lions have an Int maneSize.

trait Feline {
  def colour: String
  def sound: String
}

case class Lion(colour: String, maneSize: Int) extends Feline {
  val sound = "roar"
}

case class Tiger(colour: String) extends Feline {
  val sound = "roar"
}

case class Panther(colour: String) extends Feline {
  val sound = "roar"
}

case class Cat(colour: String, food: String) extends Feline {
  val sound = "meow"
}

trait Feline {
  def colour: String
  def sound: String = "roar"
}

trait BigCat extends Feline {
  override val sound = "roar"
}

case class Tiger(...) extends BigCat
case class Lion(...) extends BigCat
case class Panther(...) extends BigCat

4.1.4.2 Shaping Up With Traits

Define a trait called Shape and give it three abstract methods:

• sides returns the number of sides;
• perimeter returns the total length of the sides;
• area returns the area.

Implement Shape with three classes: Circle, Rectangle, and Square. In each case provide implementations of each of the three methods. Ensure that the main constructor parameters of each shape (e.g. the radius of the circle) are accessible as fields.

Tip: The value of π is accessible as math.Pi.

trait Shape {
  def sides: Int
  def perimeter: Double
  def area: Double
}

case class Circle(radius: Double) extends Shape {
  val sides = 1
  val perimeter = 2 * math.Pi * radius
  val area = math.Pi * radius * radius
}

case class Rectangle(
  width: Double,
  height: Double
) extends Shape {
  val sides = 4
  val perimeter = 2 * width + 2 * height
  val area = width * height
}

case class Square(size: Double) extends Shape {
  val sides = 4
  val perimeter = 4 * size
  val area = size * size
}

4.1.4.3 Shaping Up 2 (Da Streets)

The solution from the last exercise delivered three distinct types of shape. However, it doesn’t model the relationships between the three correctly. A Square isn’t just a Shape—it’s also a type of Rectangle where the width and height are the same.

Refactor the solution to the last exercise so that Square and Rectangle are subtypes of a common type Rectangular.

Tip: A trait can extend another trait.

// trait Shape ...

// case class Circle ...

sealed trait Rectangular extends Shape {
  def width: Double
  def height: Double
  val sides = 4
  override val perimeter = 2*width + 2*height
  override val area = width*height
}

case class Square(size: Double) extends Rectangular {
  val width = size
  val height = size
}

case class Rectangle(
  val width: Double,
  val height: Double
) extends Rectangular

4.2 This or That and Nothing Else: Sealed Traits

In many cases we can enumerate all the possible classes that can extend a trait. For example, we previously modelled a website visitor as Anonymous or a logged in User. These two cases cover all the possibilities as one is the negation of the other. We can model this case with a sealed trait, which allows the compiler to provide extra checks for us.

We create a sealed trait by simply writing sealed in front of our trait declaration:

import java.util.Date

sealed trait Visitor {
  def id: String
  def createdAt: Date
  def age: Long = new Date().getTime() - createdAt.getTime()
}

When we mark a trait as sealed we must define all of its subtypes in the same file. Once the trait is sealed, the compiler knows the complete set of subtypes and will warn us if a pattern matching expression is missing a case:

def missingCase(v: Visitor) =
  v match {
    case User(_, _, _) => "Got a user"
  }
// <console>:17: warning: match may not be exhaustive.
// It would fail on the following input: Anonymous(_, _)
//          v match {
//          ^
// error: No warnings can be incurred under -Xfatal-warnings.

We will not get a similar warning from an unsealed trait.

We can still extend the subtypes of a sealed trait outside of the file where they are defined. For example, we could extend User or Anonymous further elsewhere. If we want to prevent this possibility we should declare them as sealed (if we want to allow extensions within the file) or final if we want to disallow all extensions. For the visitors example it probably doesn’t make sense to allow any extension to User or Anonymous, so the simplified code should look like this:

sealed trait Visitor { /* ... */ }
final case class User(/* ... */) extends Visitor
final case class Anonymous(/* ... */) extends Visitor

This is a very powerful pattern and one we will use frequently.

sealed trait TraitName {
  ...
}

final case class Name(...) extends TraitName {
  ...
}

4.2.1 Take home points

Sealed traits and final (case) classes allow us to control extensibility of types. The majority of cases should use the sealed trait / final case class pattern.

sealed trait TraitName { ... }
final case class Name(...) extends TraitName

The main advantages of this pattern are:

• the compiler will warn if we miss a case in pattern matching; and
• we can control extension points of sealed traits and thus make stronger guarantees about the behaviour of subtypes.

4.2.2 Exercises

4.2.2.1 Printing Shapes

Let’s revisit the Shapes example from Section [@sec:traits:shaping-up-2].

First make Shape a sealed trait. Then write a singleton object called Draw with an apply method that takes a Shape as an argument and returns a description of it on the console. For example:

Draw(Circle(10))
// res1: String = A circle of radius 10.0cm

Draw(Rectangle(3, 4))
// res2: String = A rectangle of width 3.0cm and height 4.0cm

Finally, verify that the compiler complains when you comment out a case clause.

object Draw {
  def apply(shape: Shape): String = shape match {
    case Rectangle(width, height) =>
      s"A rectangle of width ${width}cm and height ${height}cm"

    case Square(size) =>
      s"A square of size ${size}cm"

    case Circle(radius) =>
      s"A circle of radius ${radius}cm"
  }
}

4.2.2.2 The Color and the Shape

Write a sealed trait Color to make our shapes more interesting.

• give Color three properties for its RGB values;
• create three predefined colours: Red, Yellow, and Pink;
• provide a means for people to produce their own custom Colors with their own RGB values;
• provide a means for people to tell whether any Color is “light” or “dark”.

A lot of this exercise is left deliberately open to interpretation. The important thing is to practice working with traits, classes, and objects.

Decisions such as how to model colours and what is considered a light or dark colour can either be left up to you or discussed with other class members.

Edit the code for Shape and its subtypes to add a colour to each shape.

Finally, update the code for Draw.apply to print the colour of the argument as well as its shape and dimensions:

• if the argument is a predefined colour, print that colour by name:

Draw(Circle(10, Yellow))
// res8: String = A yellow circle of radius 10.0cm

• if the argument is a custom colour rather than a predefined one, print the word “light” or “dark” instead.

You may want to deal with the colour in a helper method.

// Shape uses Color so we define Color first:
sealed trait Color {
  // We decided to store RGB values as doubles between 0.0 and 1.0.
  //
  // It is always good practice to define abstract members as `defs`
  // so we can implement them with `defs`, `vals` or `vars`.
  def red: Double
  def green: Double
  def blue: Double

  // We decided to define a "light" colour as one with
  // an average RGB of more than 0.5:
  def isLight = (red + green + blue) / 3.0 > 0.5
  def isDark = !isLight
}

case object Red extends Color {
  // Here we have implemented the RGB values as `vals`
  // because the values cannot change:
  val red = 1.0
  val green = 0.0
  val blue = 0.0
 }

case object Yellow extends Color {
  // Here we have implemented the RGB values as `vals`
  // because the values cannot change:
  val red = 1.0
  val green = 1.0
  val blue = 0.0
}

case object Pink extends Color {
  // Here we have implemented the RGB values as `vals`
  // because the values cannot change:
  val red = 1.0
  val green = 0.0
  val blue = 1.0
}

// The arguments to the case class here generate `val` declarations
// that implement the RGB methods from `Color`:
final case class CustomColor(
  red: Double,
  green: Double,
  blue: Double) extends Color

// The code from the previous exercise comes across almost verbatim,
// except that we add a `color` field to `Shape` and its subtypes:
sealed trait Shape {
  def sides: Int
  def perimeter: Double
  def area: Double
  def color: Color
}

final case class Circle(radius: Double, color: Color) extends Shape {
  val sides = 1
  val perimeter = 2 * math.Pi * radius
  val area = math.Pi * radius * radius
}

sealed trait Rectangular extends Shape {
  def width: Double
  def height: Double
  val sides = 4
  val perimeter = 2 * width + 2 * height
  val area = width * height
}

final case class Square(size: Double, color: Color) extends Rectangular {
  val width = size
  val height = size
}

final case class Rectangle(
  width: Double,
  height: Double,
  color: Color
) extends Rectangular

// We decided to overload the `Draw.apply` method for `Shape` and
// `Color` on the basis that we may want to reuse the `Color` code
// directly elsewhere:
object Draw {
  def apply(shape: Shape): String = shape match {
    case Circle(radius, color) =>
      s"A ${Draw(color)} circle of radius ${radius}cm"

    case Square(size, color) =>
      s"A ${Draw(color)} square of size ${size}cm"

    case Rectangle(width, height, color) =>
      s"A ${Draw(color)} rectangle of width ${width}cm and height ${height}cm"
  }

  def apply(color: Color): String = color match {
    // We deal with each of the predefined Colors with special cases:
    case Red    => "red"
    case Yellow => "yellow"
    case Pink   => "pink"
    case color  => if(color.isLight) "light" else "dark"
  }
}

// Test code:

Draw(Circle(10, Pink))
// res29: String = A pink circle of radius 10.0cm

Draw(Rectangle(3, 4, CustomColor(0.4, 0.4, 0.6)))
// res30: String = A dark rectangle of width 3.0cm and height 4.0cm

4.2.2.3 A Short Division Exercise

Good Scala developers don’t just use types to model data. Types are a great way to put artificial limitations in place to ensure we don’t make mistakes in our programs. In this exercise we will see a simple (if contrived) example of this—using types to prevent division by zero errors.

Dividing by zero is a tricky problem—it can lead to exceptions. The JVM has us covered as far as floating point division is concerned but integer division is still a problem:

1.0 / 0.0
// res31: Double = Infinity

1 / 0
// java.lang.ArithmeticException: / by zero
//   ... 1024 elided

Let’s solve this problem once and for all using types!

Create an object called divide with an apply method that accepts two Ints and returns DivisionResult. DivisionResult should be a sealed trait with two subtypes: a Finite type encapsulating the result of a valid division, and an Infinite type representing the result of dividing by 0.

Here’s some example usage:

val x = divide(1, 2)
// x: DivisionResult = Finite(0)

val y = divide(1, 0)
// y: DivisionResult = Infinite

Finally, write some sample code that calls divide, matches on the result, and returns a sensible description.

sealed trait DivisionResult
final case class Finite(value: Int) extends DivisionResult
case object Infinite extends DivisionResult

object divide {
  def apply(num: Int, den: Int): DivisionResult =
    if(den == 0) Infinite else Finite(num / den)
}

divide(1, 0) match {
  case Finite(value) => s"It's finite: ${value}"
  case Infinite      => s"It's infinite"
}
// res34: String = It's infinite

4.3 Modelling Data with Traits

In this section we’re going to shift our focus from language features to programming patterns. We’re going to look at modelling data and learn a process for expressing in Scala any data model defined in terms of logical ors and ands. Using the terminology of object-oriented programming, we will express is-a and has-a relationships. In the terminology of functional programming we are learning about sum and product types, which are together called algebraic data types.

Our goal in this section is to see how to translate a data model into Scala code. In the next section we’ll see patterns for code that uses algebraic data types.

4.3.1 The Product Type Pattern

Our first pattern is to model data that contains other data. We might describe this as “A has a B and C”. For example, a Cat has a colour and a favourite food; a Visitor has an id and a creation date; and so on.

The way we write this is to use a case class. We’ve already done this many times in exercises; now we’re formalising the pattern.

case class A(b: B, c: C)

trait A {
  def b: B
  def c: C
}

4.4 The Sum Type Pattern

Our next pattern is to model data that is two or more distinct cases. We might describe this as “A is a B or C”. For example, a Feline is a Cat, Lion, or Tiger; a Visitor is an Anonymous or User; and so on.

We write this using the sealed trait / final case class pattern.

sealed trait A
final case class B() extends A
final case class C() extends A

4.4.1 Algebraic Data Types

An algebraic data type is any data that uses the above two patterns. In the functional programming literature, data using the “has-a and” pattern is known as a product type, and the “is-a or” pattern is a sum type.

4.4.2 The Missing Patterns

We have looked at relationships along two dimensions: is-a/has-a, and and/or. We can draw up a little table and see we only have patterns for two of the four table cells.

What about the missing two patterns?

The “is-a and” pattern means that A is a B and C. This pattern is in some ways the inverse of the sum type pattern, and we can implement it as

trait B
trait C
trait A extends B with C

In Scala a trait can extend as many traits as we like using the with keyword like A extends B with C with D and so on. We aren’t going to use this pattern in this course. If we want to represent that some data conforms to a number of different interfaces we will often be better off using a type class, which we will explore later. There are, however, several legitimate uses of this pattern:

• for modularity, using what’s known as the cake pattern; and
• sharing implementation across several classes where it doesn’t make sense to make default implementations in the main trait.

The “has-a or” patterns means that A has a B or C. There are two ways we can implement this. We can say that A has a d of type D, where D is a B or C. We can mechanically apply our two patterns to implement this:

trait A {
  def d: D
}
sealed trait D
final case class B() extends D
final case class C() extends D

Alternatively we could implement this as A is a D or E, and D has a B and E has a C. Again this translates directly into code

sealed trait A
final case class D(b: B) extends A
final case class E(c: C) extends A

4.4.3 Take Home Points

We have seen that we can mechanically translate data using the “has-a and” and “is-a or” patterns (or, more succinctly, the product and sum types) into Scala code. This type of data is known as an algebraic data type. Understanding these patterns is very important for writing idiomatic Scala code.

4.4.4 Exercises

4.4.4.1 Stop on a Dime

A traffic light is red, green, or yellow. Translate this description into Scala code.

sealed trait TrafficLight
case object Red extends TrafficLight
case object Green extends TrafficLight
case object Yellow extends TrafficLight

4.4.4.2 Calculator

A calculation may succeed (with an Int result) or fail (with a String message). Implement this.

sealed trait Calculation
final case class Success(result: Int) extends Calculation
final case class Failure(reason: String) extends Calculation

4.4.4.3 Water, Water, Everywhere

Bottled water has a size (an Int), a source (which is a well, spring, or tap), and a Boolean carbonated. Implement this in Scala.

sealed trait Source
case object Well extends Source
case object Spring extends Source
case object Tap extends Source
final case class BottledWater(size: Int, source: Source, carbonated: Boolean)

4.5 Working With Data

In the previous section we saw how to define algebraic data types using a combination of the sum (or) and product type (and) patterns. In this section we’ll see a pattern for using algebraic data types, known as structural recursion. We’ll actually see two variants of this pattern: one using polymorphism and one using pattern matching.

Structural recursion is the precise opposite of the process of building an algebraic data type. If A has a B and C (the product-type pattern), to construct an A we must have a B and a C. The sum and product type patterns tell us how to combine data to make bigger data. Structural recursion says that if we have an A as defined before, we must break it into its constituent B and C that we then combine in some way to get closer to our desired answer. Structural recursion is essentially the process of breaking down data into smaller pieces.

Just as we have two patterns for building algebraic data types, we will have two patterns for decomposing them using structural recursion. We will actually have two variants of each pattern, one using polymorphism, which is the typical object-oriented style, and one using pattern matching, which is typical functional style. We’ll end this section with some rules for choosing which pattern to use.

4.5.1 Structural Recursion using Polymorphism

Polymorphic dispatch, or just polymorphism for short, is a fundamental object-oriented technique. If we define a method in a trait, and have different implementations in classes extending that trait, when we call that method the implementation on the actual concrete instance will be used. Here’s a very simple example. We start with a simple definition using the familiar sum type (or) pattern.

sealed trait A {
  def foo: String
}
final case class B() extends A {
  def foo: String =
    "It's B!"
}
final case class C() extends A {
  def foo: String =
    "It's C!"
}

We declare a value with type A but we see the concrete implementation on B or C is used.

val anA: A = B()
// anA: A = B()

anA.foo
// res0: String = It's B!

val anA: A = C()
// anA: A = C()

anA.foo
// res1: String = It's C!

We can define an implementation in a trait, and change the implementation in an extending class using the override keyword.

sealed trait A {
  def foo: String =
    "It's A!"
}
final case class B() extends A {
  override def foo: String =
    "It's B!"
}
final case class C() extends A {
  override def foo: String =
    "It's C!"
}

The behaviour is as before; the implementation on the concrete class is selected.

val anA: A = B()
// anA: A = B()

anA.foo
// res2: String = It's B!

Remember that if you provide a default implementation in a trait, you should ensure that implementation is valid for all subtypes.

Now we understand how polymorphism works, how do we use it with an algebraic data types? We’ve actually seen everything we need, but let’s make it explicit and see the patterns.

case class A(b: B, c: C) {
  def f: F = ???
}

sealed trait A {
  def f: F
}
final case class B() extends A {
  def f: F =
    ???
}
final case class C() extends A {
  def f: F =
    ???
}

4.5.2 Structural Recursion using Pattern Matching

Structural recursion with pattern matching proceeds along the same lines as polymorphism. We simply have a case for every subtype, and each pattern matching case must extract the fields we’re interested in.

def f(a: A): F =
  a match {
    case A(b, c) => ???
  }

def f(a: A): F =
  a match {
    case B() => ???
    case C() => ???
  }

4.5.3 A Complete Example

Let’s look at a complete example of the algebraic data type and structural recursion patterns, using our familiar Feline data type.

We start with a description of the data. A Feline is a Lion, Tiger, Panther, or Cat. We’re going to simplify the data description, and just say that a Cat has a String favouriteFood. From this description we can immediately apply our pattern to define the data.

sealed trait Feline
final case class Lion() extends Feline
final case class Tiger() extends Feline
final case class Panther() extends Feline
final case class Cat(favouriteFood: String) extends Feline

Now let’s implement a method using both polymorphism and pattern matching. Our method, dinner, will return the appropriate food for the feline in question. For a Cat their dinner is their favouriteFood. For Lions it is antelope, for Tigers it is tiger food, and for Panthers it is licorice.

We could represent food as a String, but we can do better and represent it with a type. This avoids, for example, spelling mistakes in our code. So let’s define our Food type using the now familiar patterns.

sealed trait Food
case object Antelope extends Food
case object TigerFood extends Food
case object Licorice extends Food
final case class CatFood(food: String) extends Food

Now we can implement dinner as a method returning Food. First using polymorphism:

sealed trait Feline {
  def dinner: Food
}
final case class Lion() extends Feline {
  def dinner: Food =
    Antelope
}
final case class Tiger() extends Feline {
  def dinner: Food =
    TigerFood
}
final case class Panther() extends Feline {
  def dinner: Food =
    Licorice
}
final case class Cat(favouriteFood: String) extends Feline {
  def dinner: Food =
    CatFood(favouriteFood)
}

Now using pattern matching. We actually have two choices when using pattern matching. We can implement our code in a single method on Feline or we can implement it in a method on another object. Let’s see both.

sealed trait Feline {
  def dinner: Food =
    this match {
      case Lion() => Antelope
      case Tiger() => TigerFood
      case Panther() => Licorice
      case Cat(favouriteFood) => CatFood(favouriteFood)
    }
}

object Diner {
  def dinner(feline: Feline): Food =
    feline match {
      case Lion() => Antelope
      case Tiger() => TigerFood
      case Panther() => Licorice
      case Cat(food) => CatFood(food)
    }
}

Note how we can directly apply the patterns, and the code falls out. This is the main point we want to make with structural recursion: the code follows the shape of the data, and can be produced in an almost mechanical way.

4.5.4 Choosing Which Pattern to Use

We have three way of implementing structural recursion:

1. polymorphism;
2. pattern matching in the base trait; and
3. pattern matching in an external object (as in the Diner example above).

Which should we use? The first two methods give the same result: a method defined on the classes of interest. We should use whichever is more convenient. This normally ends up being pattern matching on the base trait as it requires less code duplication.

When we implement a method in the classes of interest we can have only one implementation of the method, and everything that method requires to work must be contained within the class and parameters we pass to the method. When we implement methods using pattern matching in an external object we can provide multiple implementations, one per object (multiple Diners in the example above).

The general rule is: if a method only depends on other fields and methods in a class it is a good candidate to be implemented inside the class. If the method depends on other data (for example, if we needed a Cook to make dinner) consider implementing it using pattern matching outside of the classes in question. If we want to have more than one implementation we should use pattern matching and implement it outside the classes.

4.5.5 Object-Oriented vs Functional Extensibility

In classic functional programming style we have no objects, only data without methods and functions. This style of programming makes extensive use of pattern matching. We can mimic it in Scala using the algebraic data type pattern and pattern matching in methods defined on external objects.

Classic object oriented style uses polymorphism and allow open extension of classes. In Scala terms this means no sealed traits.

What are the tradeoffs we make in the two different styles?

One advantage of functional style is it allows the compiler to help us more. By sealing traits we are telling the compiler it knows all the possible subtypes of that trait. It can then tell us if we miss out a case in our pattern matching. This is especially useful if we add or remove subtypes later in development. We could argue we get the same benefit from object-oriented style, as we must implement all methods defined on the base trait in any subtypes. This is true, but in practice classes with a large number of methods are very difficult to maintain and we’ll inevitably end up factoring some of the code into different classes – essentially duplicating the functional style.

This doesn’t mean functional style is to be preferred in all cases. There is a fundamental difference between the kind of extensibility that object-oriented style and functional style gives us. With OO style we can easily add new data, by extending a trait, but adding a new method requires us to change existing code. With functional style we can easily add a new method but adding new data requires us to modify existing code. In tabular form:

In Scala we have the flexibility to use both polymorphism and pattern matching, and we should use whichever is appropriate. However we generally prefer sealed traits as it gives us greater guarantees about our code’s semantics, and we can use typeclasses, which we’ll explore later, to get us OO-style extensibility.

4.5.6 Exercises

4.5.6.1 Traffic Lights

In the previous section we implemented a TrafficLight data type like so:

sealed trait TrafficLight
case object Red extends TrafficLight
case object Green extends TrafficLight
case object Yellow extends TrafficLight

Using polymorphism and then using pattern matching implement a method called next which returns the next TrafficLight in the standard Red -> Green -> Yellow -> Red cycle. Do you think it is better to implement this method inside or outside the class? If inside, would you use pattern matching or polymorphism? Why?

sealed trait TrafficLight {
  def next: TrafficLight
}
case object Red extends TrafficLight {
  def next: TrafficLight =
    Green
}
case object Green extends TrafficLight {
  def next: TrafficLight =
    Yellow
}
case object Yellow extends TrafficLight {
  def next: TrafficLight =
    Red
}

sealed trait TrafficLight {
  def next: TrafficLight =
    this match {
      case Red => Green
      case Green => Yellow
      case Yellow => Red
    }
}
case object Red extends TrafficLight
case object Green extends TrafficLight
case object Yellow extends TrafficLight

4.5.6.2 Calculation

In the last section we created a Calculation data type like so:

sealed trait Calculation
final case class Success(result: Int) extends Calculation
final case class Failure(reason: String) extends Calculation

We’re now going to write some methods that use a Calculation to perform a larger calculation. These methods will have a somewhat unusual shape—this is a precursor to things we’ll be exploring soon—but if you follow the patterns you will be fine.

Create a Calculator object. On Calculator define methods + and - that accept a Calculation and an Int, and return a new Calculation. Here are some examples

assert(Calculator.+(Success(1), 1) == Success(2))
assert(Calculator.-(Success(1), 1) == Success(0))
assert(Calculator.+(Failure("Badness"), 1) == Failure("Badness"))

object Calculator {
  def +(calc: Calculation, operand: Int): Calculation = ???
  def -(calc: Calculation, operand: Int): Calculation = ???
}

object Calculator {
  def +(calc: Calculation, operand: Int): Calculation =
    calc match {
        case Success(result) => ???
        case Failure(reason) => ???
    }
  def -(calc: Calculation, operand: Int): Calculation =
    calc match {
      case Success(result) => ???
      case Failure(reason) => ???
    }
}

object Calculator {
  def +(calc: Calculation, operand: Int): Calculation =
    calc match {
        case Success(result) => Success(result + operand)
        case Failure(reason) => Failure(reason)
    }
  def -(calc: Calculation, operand: Int): Calculation =
    calc match {
      case Success(result) => Success(result - operand)
      case Failure(reason) => Failure(reason)
    }
}

Now write a division method that fails if the divisor is 0. The following tests should pass. Note the behavior for the last test. This indicates “fail fast” behavior. If a calculation has already failed we keep that failure and don’t process any more data even if, as is the case in the test, doing so would lead to another failure.

assert(Calculator./(Success(4), 2) == Success(2))
assert(Calculator./(Success(4), 0) == Failure("Division by zero"))
assert(Calculator./(Failure("Badness"), 0) == Failure("Badness"))

def /(calc: Calculation, operand: Int): Calculation =
  calc match {
    case Success(result) =>
      operand match {
        case 0 => Failure("Division by zero")
        case _ => Success(result / operand)
      }
    case Failure(reason) => Failure(reason)
  }

4.5.6.3 Email

Recall the Visitor trait we looked at earlier: a website Visitor is either Anonymous or a signed-in User. Now imagine we wanted to add the ability to send emails to visitors. We can only email signed-in users, and sending an email requires a lot of knowledge about SMTP settings, MIME headers, and so on. Would an email method be better implemented using polymorphism on the Visitor trait or using pattern matching in an EmailService object? Why?

4.6 Recursive Data

A particular use of algebraic data types that comes up very often is defining recursive data. This is data that is defined in terms of itself, and allows us to create data of potentially unbounded size (though any concrete instance will be finite).

We can’t define recursive data like⁷

final case class Broken(broken: Broken)

as we could never actually create an instance of such a type—the recursion never ends. To define valid recursive data we must define a base case, which is the case that ends the recursion.

Here is a more useful recursive definition: an IntList is either the empty list End, or a Pair⁸ containing an Int and an IntList. We can directly translate this to code using our familiar patterns:

sealed trait IntList
case object End extends IntList
final case class Pair(head: Int, tail: IntList) extends IntList

Here End is the base case. We construct the list containing 1, 2, and 3 as follows:

Pair(1, Pair(2, Pair(3, End)))

This data structure is known as a singly-linked list. In this example we have four links in our chain. We can write this out in a longer form to better understand the structure of the list. Below, d represents an empty list, and a, b, and c are pairs built on top of it.

val d = End()
val c = Pair(3, d)
val b = Pair(2, c)
val a = Pair(1, b)

In addition to being links in a chain, these data structures all represent complete sequences of integers:

• a represents the sequence 1, 2, 3
• b represents the sequence 2, 3
• c represents the sequence 3 (only one element)
• d represents an empty sequence

Using this implementation, we can build lists of arbitrary length by repeatedly taking an existing list and prepending a new element⁹.

We can apply the same structural recursion patterns to process a recursive algebraic data type. The only wrinkle is that we must make a recursive call when the data definition is recursion.

Let’s add together all the elements of an IntList. We’ll use pattern matching, but as we know the same process applies to using polymorphism.

Start with the tests and method declaration.

val example = Pair(1, Pair(2, Pair(3, End)))
assert(sum(example) == 6)
assert(sum(example.tail) == 5)
assert(sum(End) == 0)

def sum(list: IntList): Int = ???

Note how the tests define 0 to be the sum of the elements of an End list. It is important that we define an appropriate base case for our method as we will build our final result of this base case.

Now we apply our structural recursion pattern to fill out the body of the method.

def sum(list: IntList): Int =
  list match {
    case End => ???
    case Pair(hd, tl) => ???
  }

Finally we have to decide on the bodies of our cases. We have already decided that 0 is answer for End. For Pair we have two bits of information to guide us. We know we need to return an Int and we know that we need to make a recursive call on tl. Let’s fill in what we have.

def sum(list: IntList): Int =
  list match {
    case End => 0
    case Pair(hd, tl) => ??? sum(tl)
  }

The recursive call will return the sum of the tail of the list, by definition. Thus the correct thing to do is to add hd to this result. This gives us our final result:

def sum(list: IntList): Int =
  list match {
    case End => 0
    case Pair(hd, tl) => hd + sum(tl)
  }

4.6.1 Understanding the Base Case and Recursive Case

Our patterns will carry us most of the way to a correct answer, but we still need to supply the method bodies for the base and recursive cases. There is some general guidance we can use:

• For the base case we should generally return the identity for the function we’re trying to compute. The identity is an element that doesn’t change the result. E.g. 0 is the identity for addition, because a + 0 == a for any a. If we were calculating the product of elements the identity would be 1 as a * 1 == a for all a.

• For the recursive case, assume the recursion will return the correct result and work out what you need to add to get the correct answer. We saw this for sum, where we assume the recursive call will give us the correct result for the tail of the list and we then just add on the head.

sealed trait RecursiveExample
final case class RecursiveCase(recursion: RecursiveExample) extends RecursiveExample
case object BaseCase extends RecursiveExample

4.6.2 Tail Recursion

You may be concerned that recursive calls will consume excessive stack space. Scala can apply an optimisation, called tail recursion, to many recursive functions to stop them consuming stack space.

A tail call is a method call where the caller immediately returns the value. So this is a tail call

def method1: Int =
  1

def tailCall: Int =
  method1

because tailCall immediately returns the result of calling method1 while

def notATailCall: Int =
  method1 + 2

because notATailCall does not immediatley return—it adds an number to the result of the call.

A tail call can be optimised to not use stack space. Due to limitations in the JVM, Scala only optimises tail calls where the caller calls itself. Since tail recursion is an important property to maintain, we can use the @tailrec annotation to ask the compiler to check that methods we believe are tail recursion really are. Here we have two versions of sum annotated. One is tail recursive and one is not. You can see the compiler complains about the method that is not tail recursive.

import scala.annotation.tailrec

@tailrec
def sum(list: IntList): Int =
  list match {
    case End => 0
    case Pair(hd, tl) => hd + sum(tl)
  }
// <console>:20: error: could not optimize @tailrec annotated method sum: it contains a recursive call not in tail position
//          list match {
//          ^

@tailrec
def sum(list: IntList, total: Int = 0): Int =
  list match {
    case End => total
    case Pair(hd, tl) => sum(tl, total + hd)
  }
// sum: (list: IntList, total: Int)Int

Any non-tail recursion function can be transformed into a tail recursive version by adding an accumulator as we have done with sum above. This transforms stack allocation into heap allocation, which sometimes is a win, and other times is not.

In Scala we tend not to work directly with tail recursive functions as there is a rich collections library that covers the most common cases where tail recursion is used. Should you need to go beyond this, because you’re implementing your own datatypes or are optimising code, it is useful to know about tail recursion.

4.6.3 Exercises

4.6.3.1 A List of Methods

Using our definition of IntList

sealed trait IntList
case object End extends IntList
final case class Pair(head: Int, tail: IntList) extends IntList

define a method length that returns the length of the list. There is test data below you can use to check your solution. For this exercise it is best to use pattern matching in the base trait.

val example = Pair(1, Pair(2, Pair(3, End)))

assert(example.length == 3)
assert(example.tail.length == 2)
assert(End.length == 0)

sealed trait IntList {
  def length: Int =
    this match {
      case End => 0
      case Pair(hd, tl) => 1 + tl.length
    }
}
case object End extends IntList
final case class Pair(head: Int, tail: IntList) extends IntList

Define a method to compute the product of the elements in an IntList. Test cases are below.

assert(example.product == 6)
assert(example.tail.product == 6)
assert(End.product == 1)

sealed trait IntList {
  def product: Int =
    this match {
      case End => 1
      case Pair(hd, tl) => hd * tl.product
    }
}
case object End extends IntList
final case class Pair(head: Int, tail: IntList) extends IntList

Define a method to double the value of each element in an IntList, returning a new IntList. The following test cases should hold:

assert(example.double == Pair(2, Pair(4, Pair(6, End))))
assert(example.tail.double == Pair(4, Pair(6, End)))
assert(End.double == End)

sealed trait IntList {
  def double: IntList =
    this match {
      case End => End
      case Pair(hd, tl) => Pair(hd * 2, tl.double)
    }
}
case object End extends IntList
final case class Pair(head: Int, tail: IntList) extends IntList

4.6.3.2 The Forest of Trees

A binary tree of integers can be defined as follows:

A Tree is a Node with a left and right Tree or a Leaf with an element of type Int.

Implement this algebraic data type.

sealed trait Tree
final case class Node(l: Tree, r: Tree) extends Tree
final case class Leaf(elt: Int) extends Tree

Implement sum and double on Tree using polymorphism and pattern matching.

object TreeOps {
  def sum(tree: Tree): Int =
    tree match {
      case Leaf(elt) => elt
      case Node(l, r) => sum(l) + sum(r)
    }

  def double(tree: Tree): Tree =
    tree match {
      case Leaf(elt) => Leaf(elt * 2)
      case Node(l, r) => Node(double(l), double(r))
    }
}

sealed trait Tree {
  def sum: Int
  def double: Tree
}
final case class Node(l: Tree, r: Tree) extends Tree {
  def sum: Int =
    l.sum + r.sum

  def double: Tree =
    Node(l.double, r.double)
}
final case class Leaf(elt: Int) extends Tree {
  def sum: Int =
    elt

  def double: Tree =
    Leaf(elt * 2)
}

4.7 Extended Examples

To test your skills with algebraic data types and structural recursion here are some larger projects to attempt.

4.7.0.1 A Calculator

In this exercise we’ll implement a simple interpreter for programs containing only numeric operations.

We start by defining some types to represent the expressions we’ll be operating on. In the compiler literature this is known as an abstract syntax tree.

Our representation is:

• An Expression is an Addition, Subtraction, or a Number;
• An Addition has a left and right Expression;
• A Subtraction has a left and right Expression; or
• A Number has a value of type Double.

Implement this in Scala.

sealed trait Expression
final case class Addition(left: Expression, right: Expression) extends Expression
final case class Subtraction(left: Expression, right: Expression) extends Expression
final case class Number(value: Double) extends Expression

Now implement a method eval that converts an Expression to a Double. Use polymorphism or pattern matching as you see fit. Explain your choice of implementation method.

sealed trait Expression {
  def eval: Double =
    this match {
      case Addition(l, r) => l.eval + r.eval
      case Subtraction(l, r) => l.eval - r.eval
      case Number(v) => v
    }
}
final case class Addition(left: Expression, right: Expression) extends Expression
final case class Subtraction(left: Expression, right: Expression) extends Expression
final case class Number(value: Int) extends Expression

We’re now going to add some expressions that call fail: division and square root. Start by extending the abstract syntax tree to include representations for Division and SquareRoot.

sealed trait Expression
final case class Addition(left: Expression, right: Expression) extends Expression
final case class Subtraction(left: Expression, right: Expression) extends Expression
final case class Division(left: Expression, right: Expression) extends Expression
final case class SquareRoot(value: Expression) extends Expression
final case class Number(value: Double) extends Expression

Now we’re going to change eval to represent that a computation can fail. (Double uses NaN to indicate a computation failed, but we want to be helpful to the user and tell them why the computation failed.) Implement an appropriate algebraic data type.

sealed trait Calculation
final case class Success(result: Double) extends Calculation
final case class Failure(reason: String) extends Calculation

Now change eval to return your result type, which I have called Calculation in my implementation. Here are some examples:

assert(Addition(SquareRoot(Number(-1.0)), Number(2.0)).eval ==
       Failure("Square root of negative number"))
assert(Addition(SquareRoot(Number(4.0)), Number(2.0)).eval == Success(4.0))
assert(Division(Number(4), Number(0)).eval == Failure("Division by zero"))

sealed trait Expression {
  def eval: Calculation =
    this match {
      case Addition(l, r) =>
          l.eval match {
            case Failure(reason) => Failure(reason)
            case Success(r1) =>
              r.eval match {
                case Failure(reason) => Failure(reason)
                case Success(r2) => Success(r1 + r2)
              }
          }
      case Subtraction(l, r) =>
          l.eval match {
            case Failure(reason) => Failure(reason)
            case Success(r1) =>
              r.eval match {
                case Failure(reason) => Failure(reason)
                case Success(r2) => Success(r1 - r2)
              }
          }
      case Division(l, r) =>
        l.eval match {
          case Failure(reason) => Failure(reason)
          case Success(r1) =>
            r.eval match {
              case Failure(reason) => Failure(reason)
              case Success(r2) =>
                if(r2 == 0)
                  Failure("Division by zero")
                else
                  Success(r1 / r2)
            }
        }
      case SquareRoot(v) =>
        v.eval match {
          case Success(r) =>
            if(r < 0)
              Failure("Square root of negative number")
            else
              Success(Math.sqrt(r))
          case Failure(reason) => Failure(reason)
        }
      case Number(v) => Success(v)
    }
}
final case class Addition(left: Expression, right: Expression) extends Expression
final case class Subtraction(left: Expression, right: Expression) extends Expression
final case class Division(left: Expression, right: Expression) extends Expression
final case class SquareRoot(value: Expression) extends Expression
final case class Number(value: Int) extends Expression

4.7.0.2 JSON

In the calculator exercise we gave you the algebraic data type representation. In this exercise we want you to design the algebraic data type yourself. We’re going to work in what is hopefully a familiar domain: JSON.

Design an algebraic data type to represent JSON. Don’t go directly to code. Start by sketching out the design in terms of logical ands and ors—the building blocks of algebraic data types. You might find it useful to use a notation similar to BNF. For example, we could represent the Expression data type from the previous exercise as follows:

Expression ::= Addition left:Expression right:Expression
             | Subtraction left:Expression right:Expression
             | Division left:Expression right:Expression
             | SquareRoot value:Expression
             | Number value:Int

This simplified notation allows us to concentrate on the structure of the algebraic data type without worrying about the intricacies of Scala syntax.

Note you’ll need a sequence type to model JSON, and we haven’t looked at Scala’s collection library yet. However we have seen how to implement a list as an algebraic data type.

Here are some examples of JSON you’ll need to be able to represent

["a string", 1.0, true]
{
  "a": [1,2,3],
  "b": ["a","b","c"]
  "c": { "doh":true, "ray":false, "me":1 }
}

Json ::= JsNumber value:Double
       | JsString value:String
       | JsBoolean value:Boolean
       | JsNull
       | JsSequence
       | JsObject
JsSequence ::= SeqCell head:Json tail:JsSequence
             | SeqEnd
JsObject ::= ObjectCell key:String value:Json tail:JsObject
           | ObjectEnd

Translate your representation to Scala code.

sealed trait Json
final case class JsNumber(value: Double) extends Json
final case class JsString(value: String) extends Json
final case class JsBoolean(value: Boolean) extends Json
case object JsNull extends Json
sealed trait JsSequence extends Json
final case class SeqCell(head: Json, tail: JsSequence) extends JsSequence
case object SeqEnd extends JsSequence
sealed trait JsObject extends Json
final case class ObjectCell(key: String, value: Json, tail: JsObject) extends JsObject
case object ObjectEnd extends JsObject

Now add a method to convert your JSON representation to a String. Make sure you enclose strings in quotes, and handle arrays and objects properly.

object json {
  sealed trait Json {
    def print: String = {
      def quote(s: String): String =
        '"'.toString ++ s ++ '"'.toString
      def seqToJson(seq: SeqCell): String =
        seq match {
          case SeqCell(h, t @ SeqCell(_, _)) =>
            s"${h.print}, ${seqToJson(t)}"
          case SeqCell(h, SeqEnd) => h.print
        }

      def objectToJson(obj: ObjectCell): String =
        obj match {
          case ObjectCell(k, v, t @ ObjectCell(_, _, _)) =>
            s"${quote(k)}: ${v.print}, ${objectToJson(t)}"
          case ObjectCell(k, v, ObjectEnd) =>
            s"${quote(k)}: ${v.print}"
        }

      this match {
        case JsNumber(v) => v.toString
        case JsString(v) => quote(v)
        case JsBoolean(v) => v.toString
        case JsNull => "null"
        case s @ SeqCell(_, _) => "[" ++ seqToJson(s) ++ "]"
        case SeqEnd => "[]"
        case o @ ObjectCell(_, _, _) => "{" ++ objectToJson(o) ++ "}"
        case ObjectEnd => "{}"
      }
    }
  }
  final case class JsNumber(value: Double) extends Json
  final case class JsString(value: String) extends Json
  final case class JsBoolean(value: Boolean) extends Json
  case object JsNull extends Json
  sealed trait JsSequence extends Json
  final case class SeqCell(head: Json, tail: JsSequence) extends JsSequence
  case object SeqEnd extends JsSequence
  sealed trait JsObject extends Json
  final case class ObjectCell(key: String, value: Json, tail: JsObject) extends JsObject
  case object ObjectEnd extends JsObject
}

Test your method works. Here are some examples using the representation I chose.

SeqCell(JsString("a string"), SeqCell(JsNumber(1.0), SeqCell(JsBoolean(true), SeqEnd))).print
// res0: String = ["a string", 1.0, true]

ObjectCell(
  "a", SeqCell(JsNumber(1.0), SeqCell(JsNumber(2.0), SeqCell(JsNumber(3.0), SeqEnd))),
  ObjectCell(
    "b", SeqCell(JsString("a"), SeqCell(JsString("b"), SeqCell(JsString("c"), SeqEnd))),
    ObjectCell(
      "c", ObjectCell("doh", JsBoolean(true),
             ObjectCell("ray", JsBoolean(false),
               ObjectCell("me", JsNumber(1.0), ObjectEnd))),
      ObjectEnd
    )
  )
).print
// res1: String = {"a": [1.0, 2.0, 3.0], "b": ["a", "b", "c"], "c": {"doh": true, "ray": false, "me": 1.0}}

4.7.0.3 Music

In the JSON exercise there was a well defined specification to model. In this exercise we want to work on modelling skills given a rather fuzzy specification. The goal is to model music. You can choose to interpret this how you want, making your model as simple or complex as you like. The critical thing is to be able to justify the decisions you made, and to understand the limits of your model.

You might find it easiest to use the BNF notation, introduced in the JSON exercise, to write down your model.

Note ::= pitch:Pitch duration:Duration

Pitch ::= C0 | CSharp0 | D0 | DSharp0 | F0 | FSharp0 | ... | C8 | Rest

Tone ::= C | CSharp | D | DSharp | F | FSharp | ... | B

Octave ::= 0 | 1 | 2 | ... | 8

Pitch ::= tone:Tone octave:Octave

Duration ::= 0 | 1 | 2 | ...

Phrase ::= Sequence | Parallek
Sequence ::= SeqCell phrase:Phrase tail:Sequence
           | SeqEnd

Parallel ::= ParCell phrase:Phrase tail:Parallel
           | ParEnd

Sequence ::= SeqCell note:Note tail:Sequence
           | SeqEnd

Parallel ::= ParCell sequence:Sequence tail:Parallel
           | ParEnd

4.8 Conclusions

In this chapter we have made an extremely important change in our focus, away from language features and towards the programming patterns they support. This continues for the rest of the book.

We have explored two extremely important patterns: algebraic data types and structural recursion. These patterns allow us to go from a mental model of data, to the representation and processing of that data in Scala in an almost entirely mechanical way. Not only in the structure of our code formulaic, and thus easy to comprehend, but the compiler can catch common errors for us which makes development and maintenance easier. These two tools are among the most commonly used in idiomatic functional code, and it is hard to over-emphasize their importance.

In the exercises we developed a few common data structures, but we were limited to storing a fixed type of data, and our code contained a lot of repetition. In the next section we will look at how we can abstract over types and methods, and introduce some important concepts of sequencing operations.

5 Sequencing Computations

In this section we’re going to look at two more language features, generics and functions, and see some abstractions we can build using these features: functors, and monads.

Our starting point is code that we developed in the previous section. We developed IntList, a list of integers, and wrote code like the following:

sealed trait IntList {
  def length: Int =
    this match {
      case End => 0
      case Pair(hd, tl) => 1 + tl.length
    }
  def double: IntList =
    this match {
      case End => End
      case Pair(hd, tl) => Pair(hd * 2, tl.double)
    }
  def product: Int =
    this match {
      case End => 1
      case Pair(hd, tl) => hd * tl.product
    }
  def sum: Int =
    this match {
      case End => 0
      case Pair(hd, tl) => hd + tl.sum
    }
}
case object End extends IntList
final case class Pair(head: Int, tail: IntList) extends IntList

There are two problems with this code. The first is that our list is restricted to storing Ints. The second problem is that here is a lot of repetition. The code has the same general structure, which is unsurprising given we’re using our structural recursion pattern, and it would be nice to reduce the amount of duplication.

We will address both problems in this section. For the former we will use generics to abstract over types, so we can create data that works with user specified types. For the latter we will use functions to abstract over methods, so we can reduce duplication in our code.

As we work with these techniques we’ll see some general patterns emerge. We’ll name and investigate these patterns in more detail at the end of this section.

5.1 Generics

Generic types allow us to abstract over types. There are useful for all sorts of data structures, but commonly encountered in collections so that’s where we’ll start.

5.1.1 Pandora’s Box

Let’s start with a collection that is even simpler than our list—a box that stores a single value. We don’t care what type is stored in the box, but we want to make sure we preserve that type when we get the value out of the box. To do this we use a generic type.

final case class Box[A](value: A)

Box(2)
// res0: Box[Int] = Box(2)

res0.value
// res1: Int = 2

Box("hi") // if we omit the type parameter, scala will infer its value
// res2: Box[String] = Box(hi)

res2.value
// res3: String = hi

The syntax [A] is called a type parameter. We can also add type parameters to methods, which limits the scope of the parameter to the method declaration and body:

def generic[A](in: A): A = in

generic[String]("foo")
// res4: String = foo

generic(1) // again, if we omit the type parameter, scala will infer it
// res5: Int = 1

Type parameters work in a way analogous to method parameters. When we call a method we bind the method’s parameter names to the values given in the method call. For example, when we call generic(1) the name in is bound to the value 1 within the body of generic.

When we call a method or construct a class with a type parameter, the type parameter is bound to the concrete type within the method or class body. So when we call generic(1) the type parameter A is bound to Int in the body of generic.

case class Name[A](...){ ... }
trait Name[A]{ ... }

def name[A](...){ ... }

5.1.2 Generic Algebraic Data Types

We described type parameters as analogous to method parameters, and this analogy continues when extending a trait that has type parameters. Extending a trait, as we do in a sum type, is the type level equivalent of calling a method and we must supply values for any type parameters of the trait we’re extending.

In previous sections we’ve seen sum types like the following:

sealed trait Calculation
final case class Success(result: Double) extends Calculation
final case class Failure(reason: String) extends Calculation

Let’s generalise this so that our result is not restricted to a Double but can be some generic type. In doing so let’s change the name from Calculation to Result as we’re not restricted to numeric calculations anymore. Now our data definition becomes:

A Result of type A is either a Success of type A or a Failure with a String reason. This translates to the following code

sealed trait Result[A]
case class Success[A](result: A) extends Result[A]
case class Failure[A](reason: String) extends Result[A]

Notice that both Success and Failure introduce a type parameter A which is passed to Result when it is extended. Success also has a value of type A, but Failure only introduces A so it can pass it onward to Result. In a later section we’ll introduce variance, giving us a cleaner way to implement this, but for now this is the pattern we’ll use.

sealed trait A[T]
final case class B[T]() extends A[T]
final case class C[T]() extends A[T]

5.1.3 Exercises

5.1.3.1 Generic List

Our IntList type was defined as

sealed trait IntList
case object End extends IntList
final case class Pair(head: Int, tail: IntList) extends IntList

Change the name to LinkedList and make it generic in the type of data stored in the list.

sealed trait LinkedList[A]
final case class Pair[A](head: A, tail: LinkedList[A]) extends LinkedList[A]
final case class End[A]() extends LinkedList[A]

5.1.3.2 Working With Generic Types

There isn’t much we can do with our LinkedList type. Remember that types define the available operations, and with a generic type like A there isn’t a concrete type to define any available operations. (Generic types are made concrete when a class is instantiated, which is too late to make use of the information in the definition of the class.)

However, we can still do some useful things with our LinkedList! Implement length, returning the length of the LinkedList. Some test cases are below.

val example = Pair(1, Pair(2, Pair(3, End())))
assert(example.length == 3)
assert(example.tail.length == 2)
assert(End().length == 0)

sealed trait LinkedList[A] {
  def length: Int =
    this match {
      case Pair(hd, tl) => 1 + tl.length
      case End() => 0
    }
}
final case class Pair[A](head: A, tail: LinkedList[A]) extends LinkedList[A]
final case class End[A]() extends LinkedList[A]

On the JVM we can compare all values for equality. Implement a method contains that determines whether or not a given item is in the list. Ensure your code works with the following test cases:

val example = Pair(1, Pair(2, Pair(3, End())))
assert(example.contains(3) == true)
assert(example.contains(4) == false)
assert(End().contains(0) == false)
// This should not compile
// example.contains("not an Int")

sealed trait LinkedList[A] {
  def contains(item: A): Boolean =
    this match {
      case Pair(hd, tl) =>
        if(hd == item)
          true
        else
          tl.contains(item)
      case End() => false
    }
}

final case class Pair[A](head: A, tail: LinkedList[A]) extends LinkedList[A]
final case class End[A]() extends LinkedList[A]

Implement a method apply that returns the n^th item in the list

Hint: If you need to signal an error in your code (there’s one situation in which you will need to do this), consider throwing an exception. Here is an example:

throw new Exception("Bad things happened")

Ensure your solution works with the following test cases:

val example = Pair(1, Pair(2, Pair(3, End())))
assert(example(0) == 1)
assert(example(1) == 2)
assert(example(2) == 3)
assert(try {
  example(3)
  false
} catch {
  case e: Exception => true
})

sealed trait LinkedList[A] {
  def apply(index: Int): A =
    this match {
      case Pair(hd, tl) =>
        if(index == 0)
          hd
        else
          tl(index - 1)
      case End() =>
        throw new Exception("Attempted to get element from an Empty list")
    }
}
final case class Pair[A](head: A, tail: LinkedList[A]) extends LinkedList[A]
final case class End[A]() extends LinkedList[A]

Throwing an exception isn’t cool. Whenever we throw an exception we lose type safety as there is nothing in the type system that will remind us to deal with the error. It would be much better to return some kind of result that encodes we can succeed or failure. We introduced such a type in this very section.

sealed trait Result[A]
case class Success[A](result: A) extends Result[A]
case class Failure[A](reason: String) extends Result[A]

Change apply so it returns a Result, with a failure case indicating what went wrong. Here are some test cases to help you:

assert(example(0) == Success(1))
assert(example(1) == Success(2))
assert(example(2) == Success(3))
assert(example(3) == Failure("Index out of bounds"))

sealed trait Result[A]
case class Success[A](result: A) extends Result[A]
case class Failure[A](reason: String) extends Result[A]

sealed trait LinkedList[A] {
  def apply(index: Int): Result[A] =
    this match {
      case Pair(hd, tl) =>
        if(index == 0)
          Success(hd)
        else
          tl(index - 1)
      case End() =>
        Failure("Index out of bounds")
    }
}
final case class Pair[A](head: A, tail: LinkedList[A]) extends LinkedList[A]
final case class End[A]() extends LinkedList[A]

5.2 Functions

Functions allow us to abstract over methods, turning methods into values that we can pass around and manipulate within our programs.

Let’s look at three methods we wrote that manipulate IntList.

sealed trait IntList {
  def length: Int =
    this match {
      case End => 0
      case Pair(hd, tl) => 1 + tl.length
    }
  def double: IntList =
    this match {
      case End => End
      case Pair(hd, tl) => Pair(hd * 2, tl.double)
    }
  def product: Int =
    this match {
      case End => 1
      case Pair(hd, tl) => hd * tl.product
    }
  def sum: Int =
    this match {
      case End => 0
      case Pair(hd, tl) => hd + tl.sum
    }
}

case object End extends IntList
case class Pair(hd: Int, tl: IntList) extends IntList

All of these methods have the same general pattern, which is not surprising as they all use structural recursion. It would be nice to be able to remove the duplication.

Let’s start by focusing on the methods that return an Int: length, product, and sum. We want to write a method like

def abstraction(end: Int, f: ???): Int =
  this match {
    case End => end
    case Pair(hd, tl) => f(hd, tl.abstraction(end, f))
  }

I’ve used f to denote some kind of object that does the combination of the head and recursive call for the Pair case. At the moment we don’t know how to write down the type of this value, or how to construct one. However, we can guess from the title of this section that what we want is a function!

A function is like a method: we can call it with parameters and it evaluates to a result. Unlike a method a function is value. We can pass a function to a method or to another function. We can return a function from a method, and so on.

Much earlier in this course we introduced the apply method, which lets us treat objects as functions in a syntactic sense:

object add1 {
  def apply(in: Int) = in + 1
}

add1(2)
// res0: Int = 3

This is a big step towards doing real functional programming in Scala but we’re missing one important component: types.

As we have seen, types allow us to abstract across values. We’ve seen special case functions like Adders, but what we really want is a generalised set of types that allow us to represent computations of any kind.

Enter Scala’s Function types.

5.2.1 Function Types

We write a function type like (A, B) => C where A and B are the types of the parameters and C is the result type. The same pattern generalises from functions of no arguments to an arbitrary number of arguments.

In our example above we want f to be a function that accepts two Ints as parameters and returns an Int. Thus we can write it as (Int, Int) => Int.

(A, B, ...) => C

A => B

5.2.2 Function literals

Scala also gives us a function literal syntax specifically for creating new functions. Here are some example function literals:

val sayHi = () => "Hi!"
// sayHi: () => String = <function0>

sayHi()
// res1: String = Hi!

val add1 = (x: Int) => x + 1
// add1: Int => Int = <function1>

add1(10)
// res2: Int = 11

val sum = (x: Int, y:Int) => x + y
// sum: (Int, Int) => Int = <function2>

sum(10, 20)
// res3: Int = 30

In code where we know the argument types, we can sometimes drop the type annotations and allow Scala to infer them¹⁰. There is no syntax for declaring the result type of a function and it is normally inferred, but if we find ourselves needing to do this we can put a type on the function’s body expression:

(x: Int) => (x + 1): Int

(parameter: type, ...) => expression

5.2.3 Exercises

5.2.3.1 A Better Abstraction

We started developing an abstraction over sum, length, and product which we sketched out as

def abstraction(end: Int, f: ???): Int =
  this match {
    case End => end
    case Pair(hd, tl) => f(hd, tl.abstraction(end, f))
  }

Rename this function to fold, which is the name it is usually known as, and finish the implementation.

sealed trait IntList {
  def fold(end: Int, f: (Int, Int) => Int): Int =
    this match {
      case End => end
      case Pair(hd, tl) => f(hd, tl.fold(end, f))
    }

  // other methods...
}
case object End extends IntList
final case class Pair(head: Int, tail: IntList) extends IntList

Now reimplement sum, length, and product in terms of fold.

sealed trait IntList {
  def fold(end: Int, f: (Int, Int) => Int): Int =
    this match {
      case End => end
      case Pair(hd, tl) => f(hd, tl.fold(end, f))
    }
  def length: Int =
    fold(0, (_, tl) => 1 + tl)
  def product: Int =
    fold(1, (hd, tl) => hd * tl)
  def sum: Int =
    fold(0, (hd, tl) => hd + tl)
}
case object End extends IntList
final case class Pair(head: Int, tail: IntList) extends IntList

Is it more convenient to rewrite methods in terms of fold if they were implemented using pattern matching or polymorphic? What does this tell us about the best use of fold?

Why can’t we write our double method in terms of fold? Is it feasible we could if we made some change to fold?

def double: IntList =
  this match {
    case End => End
    case Pair(hd, tl) => Pair(hd * 2, tl.double)
  }

def fold(end: Int, f: (Int, Int) => Int): Int =
  this match {
    case End => end
    case Pair(hd, tl) => f(hd, tl.fold(end, f))
  }

Implement a generalised version of fold and rewrite double in terms of it.

def fold(end: Int, f: (Int, Int) => Int): Int

def fold[A](end: A, f: (Int, A) => A): A

sealed trait IntList {
  def fold[A](end: A, f: (Int, A) => A): A =
    this match {
      case End => end
      case Pair(hd, tl) => f(hd, tl.fold(end, f))
    }
  def length: Int =
    fold[Int](0, (_, tl) => 1 + tl)
  def product: Int =
    fold[Int](1, (hd, tl) => hd * tl)
  def sum: Int =
    fold[Int](0, (hd, tl) => hd + tl)
  def double: IntList =
    fold[IntList](End, (hd, tl) => Pair(hd * 2, tl))
}
case object End extends IntList
final case class Pair(head: Int, tail: IntList) extends IntList

5.3 Generic Folds for Generic Data

We’ve seen that when we define a class with generic data, we cannot implement very many methods on that class. The user supplies the generic type, and thus we must ask the user to supply functions that work with that type. Nonetheless, there are some common patterns for using generic data, which is what we explore in this section. We have already seen fold in the context of our IntList. Here we will explore fold in more detail, and learn the pattern for implementing fold for any algebraic data type.

5.3.1 Fold

Last time we saw fold we were working with a list of integers. Let’s generalise to a list of a generic type. We’ve already seen all the tools we need. First our data definition, in this instance slightly modified to use the invariant sum type pattern.

sealed trait LinkedList[A]
final case class Pair[A](head: A, tail: LinkedList[A]) extends LinkedList[A]
final case class End[A]() extends LinkedList[A]

The last version of fold that we saw on IntList was

def fold[A](end: A, f: (Int, A) => A): A =
  this match {
    case End => end
    case Pair(hd, tl) => f(hd, tl.fold(end, f))
  }

It’s reasonably straightforward to extend this to LinkedList[A]. We merely have to account for the head element of a Pair being of type A not Int.

sealed trait LinkedList[A] {
  def fold[B](end: B, f: (A, B) => B): B =
    this match {
      case End() => end
      case Pair(hd, tl) => f(hd, tl.fold(end, f))
    }
}
final case class Pair[A](head: A, tail: LinkedList[A]) extends LinkedList[A]
final case class End[A]() extends LinkedList[A]

Fold is just an adaptation of structural recursion where we allow the user to pass in the functions we apply at each case. As structural recursion is the generic pattern for writing any function that transforms an algebraic datatype, fold is the concrete realisation of this generic pattern. That is, fold is the generic transformation or iteration method. Any function you care to write on an algebraic datatype can be written in terms of fold.

Let’s apply the pattern to derive the fold method above. We start with our basic template:

sealed trait LinkedList[A] {
  def fold[B](???): B =
    this match {
      case End() => ???
      case Pair(hd, tl) => ???
    }
}
final case class Pair[A](head: A, tail: LinkedList[A]) extends LinkedList[A]
final case class End[A]() extends LinkedList[A]

This is just the structural recursion template with the addition of a generic type parameter for the return type.

Now we add one function for each of the two classes in LinkedList.

def fold[B](end: ???, pair: ???): B =
  this match {
    case End() => ???
    case Pair(hd, tl) => ???
  }

From the rules for the function types:

• end has no parameters (as End stores no values) and returns B. Thus its type is () => B, which we can optimise to just a value of type B; and
• pair has two parameters, one for the list head and one for the tail. The argument for the head has type A, and the tail is recursive and thus has type B. The final type is therefore (A, B) => B.

Substituting in we get

def fold[B](end: B, pair: (A, B) => B): B =
  this match {
    case End() => end
    case Pair(hd, tl) => pair(hd, tl.fold(end, pair))
  }

5.3.2 Working With Functions

There are a few tricks in Scala for working with functions and methods that accept functions (known as higher-order methods). Here we are going to look at:

1. a compact syntax for writing functions;
2. converting methods to functions; and
3. a way to write higher-order methods that assists type inference.

5.3.2.1 Placeholder syntax

In very simple situations we can write inline functions using an extreme shorthand called placeholder syntax. It looks like this:

((_: Int) * 2)
// res: Int => Int = <function1>

(_: Int) * 2 is expanded by the compiler to (a: Int) => a * 2. It is more idiomatic to use the placeholder syntax only in the cases where the compiler can infer the types. Here are a few more examples:

_ + _     // expands to `(a, b) => a + b`
foo(_)    // expands to `(a) => foo(a)`
foo(_, b) // expands to `(a) => foo(a, b)`
_(foo)    // expands to `(a) => a(foo)`
// and so on...

Placeholder syntax, while wonderfully terse, can be confusing for large expressions and should only be used for very small functions.

5.3.3 Converting methods to functions

Scala contains another feature that is directly relevant to this section—the ability to convert method calls to functions. This is closely related to placeholder syntax—simply follow a method with an underscore:

object Sum {
  def sum(x: Int, y: Int) = x + y
}

Sum.sum
// <console>:23: error: missing argument list for method sum in object Sum
// Unapplied methods are only converted to functions when a function type is expected.
// You can make this conversion explicit by writing `sum _` or `sum(_,_)` instead of `sum`.
//        Sum.sum
//            ^

(Sum.sum _)
// res1: (Int, Int) => Int = <function2>

In situations where Scala can infer that we need a function, we can even drop the underscore and simply write the method name—the compiler will promote the method to a function automatically:

object MathStuff {
  def add1(num: Int) = num + 1
}

Counter(2).adjust(MathStuff.add1)
// res2: Counter = Counter(3)

5.3.3.1 Multiple Parameter Lists

Methods in Scala can actually have multiple parameter lists. Such methods work just like normal methods, except we must bracket each parameter list separately.

def example(x: Int)(y: Int) = x + y
// example: (x: Int)(y: Int)Int

example(1)(2)
// res3: Int = 3

Multiple parameter lists have two relevant uses: they look nicer when defining functions inline and they assist with type inference.

The former is the ability to write functions that look like code blocks. For example, if we define fold as

def fold[B](end: B)(pair: (A, B) => B): B =
  this match {
    case End() => end
    case Pair(hd, tl) => pair(hd, tl.fold(end, pair))
  }

then we can call it as

fold(0){ (total, elt) => total + elt }

which is a bit easier to read than

fold(0, (total, elt) => total + elt)

More important is the use of multiple parameter lists to ease type inference. Scala’s type inference algorithm cannot use a type inferred for one parameter for another parameter in the same list. For example, given fold with a signature like

def fold[B](end: B, pair: (A, B) => B): B

if Scala infers B for end it cannot then use this inferred type for the B in pair, so we must often write a type declaration on pair. However, Scala can use types inferred for one parameter list in another parameter list. So if we write fold as

def fold[B](end: B)(pair: (A, B) => B): B

then inferring B from end (which is usually easy) allows B to be used when inferring the type pair. This means fewer type declarations and a smoother development process.

5.3.4 Exercises

5.3.4.1 Tree

A binary tree can be defined as follows:

A Tree of type A is a Node with a left and right Tree or a Leaf with an element of type A.

Implement this algebraic data type along with a fold method.

sealed trait Tree[A] {
  def fold[B](node: (B, B) => B, leaf: A => B): B
}
final case class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A] {
  def fold[B](node: (B, B) => B, leaf: A => B): B =
    node(left.fold(node, leaf), right.fold(node, leaf))
}
final case class Leaf[A](value: A) extends Tree[A] {
  def fold[B](node: (B, B) => B, leaf: A => B): B =
    leaf(value)
}

Using fold convert the following Tree to a String

val tree: Tree[String] =
  Node(Node(Leaf("To"), Leaf("iterate")),
       Node(Node(Leaf("is"), Leaf("human,")),
            Node(Leaf("to"), Node(Leaf("recurse"), Leaf("divine")))))

Remember you can append Strings using the + method.

tree.fold[String]((a, b) => a + " " + b, str => str)

5.4 Modelling Data with Generic Types

In this section we’ll see the additional power the generic types give us when modelling data. We see that with generic types we can implement generic sum and product types, and also model some other useful abstractions such as optional values.

5.4.1 Generic Product Types

Let’s look at using generics to model a product type. Consider a method that returns two values—for example, an Int and a String, or a Boolean and a Double:

def intAndString: ??? = // ...

def booleanAndDouble: ??? = // ...

The question is what do we use as the return types? We could use a regular class without any type parameters, with our usual algebraic data type patterns, but then we would have to implement one version of the class for each combination of return types:

case class IntAndString(intValue: Int, stringValue: String)

def intAndString: IntAndString = // ...

case class BooleanAndDouble(booleanValue: Boolean, doubleValue: Double)

def booleanAndDouble: BooleanAndDouble = // ...

The answer is to use generics to create a product type—for example a Pair—that contains the relevant data for both return types:

def intAndString: Pair[Int, String] = // ...

def booleanAndDouble: Pair[Boolean, Double] = // ...

Generics provide a different approach to defining product types— one that relies on aggregation as opposed to inheritance.

5.4.1.1 Exercise: Pairs

Implement the Pair class from above. It should store two values—one and two—and be generic in both arguments. Example usage:

val pair = Pair[String, Int]("hi", 2)
// pair: Pair[String,Int] = Pair(hi,2)

pair.one
// res0: String = hi

pair.two
// res1: Int = 2

case class Pair[A, B](one: A, two: B)

val pair = Pair("hi", 2)
// pair: Pair[String,Int] = Pair(hi,2)

5.4.2 Tuples

A tuple is the generalisation of a pair to more terms. Scala includes built-in generic tuple types with up to 22 elements, along with special syntax for creating them. With these classes we can represent any kind of this and that relationship between almost any number of terms.

The classes are called Tuple1[A] through to Tuple22[A, B, C, ...] but they can also be written in the sugared¹¹ form (A, B, C, ...). For example:

Tuple2("hi", 1) // unsugared syntax
// res2: (String, Int) = (hi,1)

("hi", 1) // sugared syntax
// res3: (String, Int) = (hi,1)

("hi", 1, true)
// res4: (String, Int, Boolean) = (hi,1,true)

We can define methods that accept tuples as parameters using the same syntax:

def tuplized[A, B](in: (A, B)) = in._1
// tuplized: [A, B](in: (A, B))A

tuplized(("a", 1))
// res5: String = a

We can also pattern match on tuples as follows:

(1, "a") match {
  case (a, b) => a + b
}
// res6: String = 1a

Although pattern matching is the natural way to deconstruct a tuple, each class also has a complement of fields named _1, _2 and so on:

val x = (1, "b", true)
// x: (Int, String, Boolean) = (1,b,true)

x._1
// res7: Int = 1

x._3
// res8: Boolean = true

5.4.3 Generic Sum Types

Now let’s look at using generics to model a sum type. Again, we have previously implemented this using our algebraic data type pattern, factoring out the common aspects into a supertype. Generics allow us to abstract over this pattern, providing a … well … generic implementation.

Consider a method that, depending on the value of its parameters, returns one of two types:

def intOrString(input: Boolean) =
  if(input == true) 123 else "abc"
// intOrString: (input: Boolean)Any

We can’t simply write this method as shown above because the compiler infers the result type as Any. Instead we have to introduce a new type to explicitly represent the disjunction:

def intOrString(input: Boolean): Sum[Int, String] =
  if(input == true) {
    Left[Int, String](123)
  } else {
    Right[Int, String]("abc")
  }
// intOrString: (input: Boolean)sum.Sum[Int,String]

How do we implement Sum? We just have to use the patterns we’ve already seen, with the addition of generic types.

5.4.3.1 Exercise: Generic Sum Type

Implement a trait Sum[A, B] with two subtypes Left and Right. Create type parameters so that Left and Right can wrap up values of two different types.

Hint: you will need to put both type parameters on all three types. Example usage:

Left[Int, String](1).value
// res9: Int = 1

Right[Int, String]("foo").value
// res10: String = foo

val sum: Sum[Int, String] = Right("foo")
// sum: sum.Sum[Int,String] = Right(foo)

sum match {
  case Left(x) => x.toString
  case Right(x) => x
}
// res11: String = foo

sealed trait Sum[A, B]
final case class Left[A, B](value: A) extends Sum[A, B]
final case class Right[A, B](value: B) extends Sum[A, B]

5.4.4 Generic Optional Values

Many expressions may sometimes produce a value and sometimes not. For example, when we look up an element in a hash table (associative array) by a key, there may not be a value there. If we’re talking to a web service, that service may be down and not reply to us. If we’re looking for a file, that file may have been deleted. There are a number of ways to model this situation of an optional value. We could throw an exception, or we could return null when a value is not available. The disadvantage of both these methods is they don’t encode any information in the type system.

We generally want to write robust programs, and in Scala we try to utilise the type system to encode properties we want our programs to maintain. One common property is “correctly handle errors”. If we can encode an optional value in the type system, the compiler will force us to consider the case where a value is not available, thus increasing the robustness of our code.

5.4.4.1 Exercise: Maybe that Was a Mistake

Create a generic trait called Maybe of a generic type A with two subtypes, Full containing an A, and Empty containing no value. Example usage:

val perhaps: Maybe[Int] = Empty[Int]

val perhaps: Maybe[Int] = Full(1)

sealed trait Maybe[A]
final case class Full[A](value: A) extends Maybe[A]
final case class Empty[A]() extends Maybe[A]

5.4.5 Take Home Points

In this section we have used generics to model sum types, product types, and optional values using generics.

These abstractions are commonly used in Scala code and have implementations in the Scala standard library. The sum type is called Either, products are tuples, and optional values are modelled with Option.

5.4.6 Exercises

5.4.6.1 Generics versus Traits

Sum types and product types are general concepts that allow us to model almost any kind of data structure. We have seen two methods of writing these types—traits and generics. When should we consider using each?