Chapter 8. Building scalable and extensible components

This chapter covers

• Building components in Scala
• A tour of various types of types in Scala
• Ad hoc polymorphism with type classes
• Solving expression problems in Scala

So far we’ve been working with Scala without paying any serious attention to its type system. The type system is a tractable syntactic method for proving the absence of certain program behaviors by classifying phrases according to the kinds of values they compute.^[1]

¹ Benjamin C. Pierce, Types and Programming Languages, 2002, The MIT Press, www.cis.upenn.edu/~bcpierce/tapl/.

The challenge of learning about a type system is understanding the theory behind it. It’s always helpful to learn the fundamentals behind a good type system, but in this chapter my focus is on the practical benefits of a good type system without going too much into theory. In the process I explore various types of the types Scala provides you, with examples so you can understand their applications. Why is the type system so important? It provides the following features:

• Error detection— Think of the compiler as a suite of test cases that can detect common type and other program errors.
• Abstractions— This is the focus of this chapter. You’ll learn how the type system provides abstractions to build components.
• Documentation— The signature of a function or method tells you a lot about what it’s doing.
• Efficiency— The type system helps the compiler generate optimized binary code.

My goal for this chapter is to show you how you can use Scala’s type system to build reusable components. I’m using component as an umbrella term to refer to reusable libraries, classes, modules, frameworks, or web services.

Building reusable components is not easy. The goal of building software by assembling components is still a dream and isn’t possible to the extent we’d like. The challenge of building something reusable is to make the components refer to the context in which they are built. Typically, you modify your component to suit the current need and end up with multiple versions of the same component. This results in a maintenance problem. In the first section of this chapter, you’ll learn about building simple, reusable components using Scala’s type system.

Next you’ll learn about different kinds of types provided by Scala so that you’re aware of all the building blocks you have to make your code more expressive and reusable.

You’ll also learn about a new kind of polymorphism using type classes that allows you to express and create abstractions that are easy to extend and scale—a powerful construct to help you solve your day-to-day programming problems.

It’s important to understand that a good type system doesn’t work against you. Rather, it provides you with enough flexibility to be as creative as possible. Settle in with your coffee and don’t worry if the ride feels a little bumpy. I promise, by the end of this chapter the results will be valuable.

8.1. Building your first component in Scala

As I mentioned, building scalable and reusable components is hard. By scalable I mean small or large components—particularly when you’re trying to build one using a type-safe, object-oriented language. Table 8.1 explores three abstraction techniques provided by Scala.

Table 8.1. Scala abstraction techniques

I covered mixin composition in detail in chapter 3. Remember that Scala traits allow you to build small components and combine them to build larger components. Let’s explore abstract type members and self type before you start building your component, because they’re important building blocks.

8.1.1. Abstract type members

Scala takes the idea of abstract beyond methods and fields. You can also declare abstract type members inside a class or trait. Abstract types are those whose identity is unknown at the time of declaration. Unlike concrete types, the type of an abstract type member is specified during the concrete implementation of the enclosing class. The following example declares an abstract type member S inside a trait called Calculator:

trait Calculator { type S }

Any concrete class that mixes in this trait has to now provide a type for an S type member:

class SomeCalculator extends Calculator { type S = String }

The benefit of abstract type members is they can hide the internal information of a component. I’ll use an example to demonstrate that fact. You’re going to build a price calculator that can take a product ID and return the price of the product. There can be many ways to calculate the price, and each way could use a different type of data source to retrieve the price. You’re building this for a retail company that sells various types of products from a number of manufacturers. The common steps across all the calculators are the following:

1.  Connect to a data source (could be of many types)

2.  Calculate the price using the data source

3.  Close the connection to the data source

A fairly successful way to encode common steps and program skeletons is a Template Method pattern, which lets you follow a common algorithm across multiple subclasses. Here’s how you could implement your parent Calculator trait using the Template Method pattern:

trait Calculator {
    def initialize: DbConnection
    def close(s: DbConnection): Unit
    def calculate(productId: String): Double = {
      val s = initialize
      val price = calculate(s, productId)
      close(s)
      price
    }
    def calculate(s: DbConnection, productId: String): Double
  }

In this example, DbConnection is a component that knows how to retrieve data from a database. Because all the necessary steps are implemented, each calculator can implement the overloaded calculate(s: DAO, productId: String) method. The problem with the current implementation is that it’s hard-wired to a DAO, and a calculator that uses a different kind of data source won’t be able to use the calculator.

You can easily fix the problem of the hard link to DbConnection by creating an abstract type member that hides the type of component you use to retrieve the price from the data source. The following listing shows the Calculator trait with the abstract type member.

Listing 8.1. Calculator trait with abstract type member

package abstractMember {
  trait Calculator {
    type S
    def initialize: S
    def close(s: S): Unit
    def calculate(productId: String): Double = {
      val s = initialize
      val price = calculate(s, productId)
      close(s)
      price
    }
    def calculate(s: S, productId: String): Double
  }
}

The Calculator trait abstracts out the type that knows how to connect to the data source. The initialize method makes the connection to a data source, and the close method closes the connection. Now any concrete calculator implementation, along with implementing all the abstract methods, needs to provide type information for S. Here’s one implementation of a calculator that uses MongoDB as a data source:

class CostPlusCalculator extends Calculator {
    type S = MongoClient
    def initialize = new MongoClient
    def close(dao: MongoClient) = dao.close

    def calculate(source: MongoClient, productId: String) = {
      ...
    }
  }
  class MongoClient {
    def close = ...
  }

The abstract type member concept is particularly useful to model a family of types that varies covariantly. The next section talks about self type, which helps in building components from smaller components.

8.1.2. Self type members

The self type annotation allows you to access members of a mixin trait or class, and the Scala compiler ensures that all the dependencies are correctly wired before you’re allowed to instantiate the class. Self type makes mixin composition more powerful because it allows you to statically define dependencies defined by other classes and traits. In the following example, trait A is defining a dependency to trait B:

Trait A can’t be mixed in with a concrete class unless that class also extends B. And because of that type-safety, you can access members of B as if it’s defined in A, as shown in the preceding example. Also note that self is a name—it could be any valid parameter name. The most common names used for self type annotation are this and self.

I’ll use an example to demonstrate how self type can work in a real-world application. In this example, you’ll try to build a product finder that depends on a couple of required services: a way to access the database and a logger to log the result. Because traits let you easily compose features, separate the required services and the logic to find products into separate traits. Here are the required service traits:

trait Connection {
  def query(q: String): String
}

trait Logger {
  def log(l: String): Unit
}

trait RequiredServices {
  def makeDatabaseConnection: Connection
  def logger: Logger
}

The RequiredServices trait declares all the services that could be used by the product finder:

trait ProductFinder { this: RequiredServices =>
   def findProduct(productId: String) = {
     val c = makeDatabaseConnection
     c.query("find the lowest price")
     logger.log("querying database...")
   }
 }

Because the required services are annotated with self type this, you can still access those services, and the Scala compiler will ensure that the final class gets mixed with a trait or a class that implements RequiredServices. The following listing shows the complete example with test services.

Listing 8.2. Product finder with self type annotation

This example shows how to build large components by combining smaller components in Scala using self type annotation and mixin composition. We will explore self type once again in chapter 10 to help in unit testing. Now let’s move on to build your first reusable component—a generic ordering system.

8.1.3. Building a scalable component

To see how to build a reusable component, let’s build a generic product ordering system. It will be reusable in that a user can order any kind of product. A general ordering system is built using the following components (see figure 8.1):

Figure 8.1. Ordering system with three components: order, inventory, and shipping

• An order component that represents the order placed by the customer.
• An inventory component that stores the products. You need to check the inventory to make sure you have the product before you place the order.
• A shipping component that knows how to ship an order to customer.

A real-world ordering system is more complex than this, but let’s stick to this simple system because you can easily scale it to fit into a larger context.

You can use abstract type members to abstract out the components your ordering system requires:

trait OrderingSystem {
  type O <: Order
  type I <: Inventory
  type S <: Shipping
}

The OrderingSystem declares three abstract members—O, I, and S—and at the same time sets the upper bounds for each type. The type O denotes a type that is a subtype of the Order type. Similarly I and S should be a subtype of Inventory and Shipping. And Order, Inventory, and Shipping define the contracts for each component:

trait OrderingSystem {
  type O <: Order
  type I <: Inventory
  type S <: Shipping

  trait Order {def placeOrder (i: I):Unit }
  trait Inventory { def itemExists(order: O): Boolean }
  trait Shipping {def scheduleShipping(order: O): Long }
}

The benefit of nesting all these components under a trait is that they’re all aggregated and encapsulated in one place. So far you have the interfaces for each component, but you still need to implement the steps for placing the order. Here they are:

1.  Check whether that item exists in inventory.

2.  Place the order against the inventory. (Inventory will reduce the count by the amount of product in the inventory.)

3.  Schedule the order for shipping.

4.  If the item doesn’t exist in inventory, return without placing the order and possibly notify Inventory to replenish the product.

Let’s implement these steps as part of an Ordering trait that is defined inside the OrderingSystem:

The placeOrder method implements all the steps mentioned with the help of the self type annotation. Ordering now relies on Inventory for itemExists and Shipping for the scheduleShipping method. Note that you can specify multiple self type annotations using the with keyword, similar to the way you mix in traits. All these pieces together make up the ordering system component. The following listing shows the complete code.

Listing 8.3. Generic ordering system with abstract type members and self type

The abstract type members of the OrderingSystem represent the required services that this component relies on without providing concrete implementation. This allows it to be reusable in various contexts. The mixin feature allows it to build the Ordering trait by composing Inventory and Shipping traits. And finally self type allows the Ordering trait to use services provided by the mixed in traits. As you can see, all these abstracts provide a building block to build scalable and reusable components in Scala. If you want to implement an ordering system for books, you could easily use the OrderingSystem as follows:

object BookOrderingSystem extends OrderingSystem {
  type O = BookOrder
  type I = AmazonBookStore
  type S = UPS

  class BookOrder extends Order {
     def placeOrder(i: AmazonBookStore): Unit = ...
  }
  trait AmazonBookStore extends Inventory {
    def itemExists(o: BookOrder) = ...
  }

  trait UPS extends Shipping {
    def scheduleShipping(order: BookOrder): Long = ...
  }

  object BookOrdering extends Ordering with AmazonBookStore with UPS
}

The BookOrderingSystem provides all the concrete implementations and creates the BookOrdering object to place orders for books. Now all you have to do to use the BookOrderingSystem is import it:

import BookOrderingSystem._
BookOrdering.placeOrder(new BookOrder)

The next section shows you how to use the concepts you learned here to solve the expression problem.

8.1.4. Building an extensible component

The ability to extend a software component and integrate it into an existing software system without changing existing source code is a fundamental challenge in software engineering. Many people have used the expression problem to demonstrate that object-oriented inheritance fails in terms of extensibility of a software component. The expression problem is one in which the challenge is to define a data type with cases, and in which one can add new cases of the type, and operations for the types, without recompiling and maintaining static type-safety. Usually this challenge is used to demonstrate strength and weakness of programming languages. Next I’ll show you how to solve the expression problem in Scala with the constructs you’ve learned so far. But first lets look at the expression problem in detail.

The Expression Problem and the Extensibility Challenge

The goal is to define a data type and operations on that data type in which one can add new data types and operations without recompiling existing code, but while retaining static type safety.

Any implementation of the expression problem should satisfy the following requirements:

• Extensibility in both dimensions. You should be able to add new types and operations that work on all the types. (I look into this in detail in this section.)
• Strong static type-safety. Type casting and reflection are out of the question.
• No modification of the existing code and no duplication.
• Separate compilation.

Let’s explore this problem with a practical example. You have a payroll system that processes salaries for full-time employees in the United States and Canada:

case class Employee(name: String, id: Long)

trait Payroll {
  def processEmployees(
    employees: Vector[Employee]): Either[String, Throwable]
}

class USPayroll extends Payroll {
  def processEmployees(employees: Vector[Employee]) = ...
}

class CanadaPayroll extends Payroll {
  def processEmployees(employees: Vector[Employee]) = ...
}

The Payroll trait declares the processEmployees method that takes a collection of employees and processes their salaries. It returns Either because it could succeed or fail. Both USPayroll and CanadaPayroll implement the processEmployees method based on the way the salary is processed in the individual country.

With current changes in the business, you also have to process salaries of full-time employees in Japan. That’s easy—all you have to do is add another class that extends the Payroll trait:

class JapanPayroll extends Payroll {
  def processEmployees(employees: Vector[Employee]) = ...
}

This is one type of extension the expression problem talks about. The solution is type-safe, and you can add JapanPayroll as an extension and plug it in to an existing payroll system with a separate compilation.

What happens when you try to add a new operation? In this case the business has decided to hire contractors, and you also have to process their monthly pay. The new Payroll interface should look like the following:

case class Employee(name: String, id: Long)
case class Contractor(name: String)

trait Payroll extends super.Payroll {
   def processEmployees(
    employees: Vector[Employee]): Either[String, Throwable]
   def processContractors(
    contractors: Vector[Contractor]): Either[String, Throwable]
}

The problem is you can’t go back and modify the trait because that will force you to rebuild everything—which you can’t do because of the constraint put on you by the expression problem. This is a practical problem: how to add features to an existing system incrementally without doing modifications. To understand the difficulty of solving the expression problem, let’s try another route: using the Visitor pattern to solve this problem. You’ll have one Visitor to process salaries for employees:

case class USPayroll {
    def accept(v: PayrollVisitor) = v.visit(this)
}

case class CanadaPayroll {
   def accept(v: PayrollVisitor) = v.visit(this)
}

trait PayrollVisitor {
   def visit(payroll: USPayroll): Either[String, Throwable]
   def visit(payroll: CanadaPayroll): Either[String, Throwable]
}

class EmployeePayrollVisitor extends PayrollVisitor {
   def visit(payroll: USPayroll): Either[String, Throwable] = ...
   def visit(payroll: CanadaPayroll): Either[String, Throwable] = ...
}

Both the USPayroll and CanadaPayroll types accept a payroll visitor. To process salaries for employees, you’ll use an instance of EmployeePayrollVisitor. To process monthly pay for contractors, you can easily create a new class called ContractorPayrollVisitor, as in the following:

class ContractorPayrollVisitor extends PayrollVisitor {
   def visit(payroll: USPayroll): Either[String, Throwable] = ...
   def visit(payroll: CanadaPayroll): Either[String, Throwable] = ...
}

Using the Visitor pattern, it’s easy to add new operations, but what about type? If you try to add a new type called JapanPayroll, you have a problem. You have to go back and change all the visitors to accept a JapanPayroll type. In the first solution it was easy to add a new type, and in the second solution it’s easy to add an operation. But you want a solution that lets you change in both dimensions. In the next section you’ll learn how to solve this problem in Scala using abstract type members and trait mixins.

Solving the Expression Problem

You’ll use Scala traits and abstract type members to solve the expression problem. Using the same payroll system, I’ll show you how to easily add new operations to the payroll system without breaking type-safety and at the same time add a new type.

Start by defining the base payroll system as a trait with an abstract type member for payroll:

Again you’ll nest everything inside a trait so that you can treat it as a module. The type P denotes some subtype of the Payroll trait, which declares an abstract method to process salaries for employees. The processPayroll method needs to be implemented to process payrolls for a given Payroll type. Here’s how the trait could be extended for U.S. and Canada payrolls:

trait USPayrollSystem extends PayrollSystem {
  class USPayroll extends Payroll {
    def processEmployees(employees: Vector[Employee]) =
      Left("US payroll")
  }
}

trait CanadaPayrollSystem extends PayrollSystem {
  class CanadaPayroll extends Payroll {
    def processEmployees(employees: Vector[Employee]) =
       Left("Canada payroll")  }
}

I’ve omitted the details of processing a payroll because it’s not important in this context. To process the payroll for U.S. employees, you can implement a USPayrollSystem by providing an implementation of the processPayroll method:

object USPayrollInstance extends USPayrollSystem {
  type P = USPayroll
  def processPayroll(p: USPayroll) = {
    val employees: Vector[Employee] = ...
    val result = p.processEmployees(employees)
    ...
  }
}

In these settings it will be easy to add a new Payroll type for Japan. Create a trait that extends the PayrollSystem:

trait JapanPayrollSystem extends PayrollSystem {
  class JapanPayroll extends Payroll {
    def processEmployees(employees: Vector[Employee]) = ...
  }
}

Now add a new method to the Payroll trait without recompiling everything, using the shadowing feature of Scala:

The Payroll trait defined inside the ContractorPayrollSystem doesn’t override but instead shadows the former definition of Payroll type from PayrollSystem. The former definition of Payroll is accessible in the context of ContractPayrollSystem using the super keyword. Shadowing can introduce unintended errors in your code, but in this context it lets you extend the old definition of Payroll without overriding it.

Another thing to notice is that you’re redefining the abstract type member P. P needs to be any subtype of Payroll that understands both the processEmployees and processContractors methods. To process contractors for both the U.S. and Canada, extend the ContractPayrollSystem trait:

trait USContractorPayrollSystem extends USPayrollSystem with
   ContractorPayrollSystem {

  class USPayroll extends super.USPayroll with Payroll {
    def processContractors(contractors: Vector[Contractor]) =
      Left("US contract payroll")
  }
}

trait CanadaContractorPayrollSystem extends CanadaPayrollSystem with
   ContractorPayrollSystem {

  class CanadaPayroll extends super.CanadaPayroll with Payroll {
    def processContractors(contractors: Vector[Contractor]) =
       Left("Canada contract payroll")
  }
}

You’re shadowing the former definition of USPayroll and CanadaPayroll. Also note that you’re mixing in the new definition of the Payroll trait to implement the processContractors method. Keep type-safety requirements in mind: if you don’t mix in the Payroll trait, you’ll get an error when you try to create a concrete implementation of the USContractorPayrollSystem or CanadaContractorPayrollSystem. Similarly you can add the processContractors operation to JapanPayrollSystem:

trait JapanContractorPayrollSystem extends JapanPayrollSystem with
  ContractorPayrollSystem {

  class JapanPayroll extends super.JapanPayroll with Payroll {
    def processContractors(contractors: Vector[Contractor]) =
      Left("Japan contract payroll")
  }
}

At this point you’ve successfully solved the expression problem. The following listing shows the complete example.

Listing 8.4. Solution to the expression problem using PayrollSystem

Using Scala first-class module support, you can wrap all the traits and classes inside an object and extend an existing software component without forcing everything to recompile and at the same time maintain type-safety. Note that both old and new interfaces of the Payroll are available, and the behavior is driven by what traits you compose. To use the new Payroll so you can process both employees and contractors, you have to mix in one of the ContractorPayrollSystem traits. The following example demonstrates how you can create an instance of USContractorPayrollSystem and use it:

The processPayroll method invokes both the processEmployees and processContractors methods of the Payroll trait, but you could instead have easily used an existing payroll system that knows how to process salaries for U.S. employees, because you’re still confirming the USPayroll trait. All that remains is to implement the additional processContractors part.

This is a good example that demonstrates the power of Scala’s type system and the abstractions available to build both scalable and extensible components. We solved this problem using the object-oriented abstractions available in Scala. In section 8.3, I’ll show you how to solve this problem using the functional programming side of things. But first I’ll go over another powerful type of abstraction available in Scala.

8.2. Types of types in Scala

One of Scala’s unique features is its rich type system. Like any good type system, it doesn’t work against you but rather provides the abstractions necessary to build reusable components. This section explores various types offered by the Scala type system.

8.2.1. Structural types

Structural typing in Scala is the way to describe types by their structure, not by their names, as with other typing. If you’ve used dynamically typed languages, a structural type may give you the feel of duck typing (a style of dynamic typing) in a type-safe manner. Let’s say you want to close any resource after use as long as it’s closable. One way to do that would be to define a trait that declares a close method and have all the resources implement the trait. But using a structural type, you can easily define a new type by specifying its structure, like the following:

def close(closable: { def close: Unit }) = {
   closable.close
}

The type of the parameter is defined by the { def close: Unit } structure. The flexibility of this approach is that now you can pass instances of any type to this function as long as it implements the def close: Unit method. Currently this new type doesn’t have any name, but using the type keyword you can easily provide a name (type alias):

type Closable = { def close: Unit }
def close(closable: { def close: Unit }) = {
  closable.close
}

Structural types aren’t limited to a single method, but when defining multiple methods make sure you use the type keyword to give it a name—otherwise, your function signatures will look confusing:

type Profile = {
  def name: String
  def address: String
}

You can also create new values of a structural type using the new keyword. For example:

val nilanjanProfile = new {
   def name = "Nilanjan"
   def address = "Boulder, CO"
}

You can use a structural type to reduce class hierarchies and simplify a code base. Let’s say you have the following class hierarchies to represent various types of workers for a department store:

trait Worker {
  def salary: BigDecimal
     def bonusPercentage: Double
}

trait HourlyWorker {
  def hours: Int
  def salary: BigDecimal
}

case class FullTimeWorker(val salary: BigDecimal, ...)
    extends Worker
case class PartTimeWorker(val hours: Int, val salary: BigDecimal, ...)
    extends HourlyWorker
case class StudentWorker(val hours: Int, val salary: BigDecimal, ...)
     extends HourlyWorker

This is a small hierarchy, but you get the idea. Each type of worker is different; there are hourly and full-time workers. The only thing they have in common is they all get paid. If you have to calculate the money spent on paying salaries to workers in a given month, you have to define another common type that represents salaried workers:

trait SalariedWorker {
  def salary: BigDecimal
}

trait Worker extends SalariedWorker {
  def bonusPercentage: Double
}

trait HourlyWorker extends SalariedWorker {
  def hours: Int
}

def amountPaidAsSalary(workers: Vector[SalariedWorker]) = {
  ...
}

The benefit of duck typing is that it lets you abstract out commonalities without being part of the same type. Using a structural type you can easily rewrite a function like the following without defining new types:

def amountPaidAsSalary2(workers: Vector[{def salary: BigDecimal }]) = {
}

Now you can pass instances of any worker to the previous function without conforming to some common type. Structural type is a good technique to get rid of unnecessary class hierarchies, but the downside is that it’s comparatively slow because it uses reflection under the hood.

8.2.2. Higher-kinded types

Higher-kinded types are types that know how to create a new type from the type argument. That’s why higher-kinded types are also known as type constructors—they accept other types as a parameter and create a new type. The scala.collections.immutable.List[+A] is an example of a higher-kinded type. It takes a type parameter and creates a new concrete type. List[String] and List[Int] are examples of types you can create from the List kind. Kinds are to types as types are to values (see figure 8.2).

Figure 8.2. Types classify values, and kinds classify types.

Most of the collections classes are good examples of why kinds are such a powerful abstraction tool. You saw examples using higher-kinded types in chapter 5. Let’s look at more examples to understand their usefulness. You’ll try to build a function that takes another function as a parameter and applies that function to elements of a given type. For example, you have a vector of elements and want to apply a function to each element of the vector:

def fmap[A, B](xs: Vector[A], f: A => B): Vector[B] = xs map f

fmap applies the given f function to all the elements of vector. Similarly, if you want to apply the function to Option, you have to create another function:

def fmap[A, B](r: Option[A], f: A => B): Option[B] = r map f

Both functions look similar and only differ by the first parameter. The question is: how can you define a common fmap function signature for various types? Using a higher-kinded type, you can abstract out the type of the first parameter, as in the following:

trait Mapper[F[_]] {
      def fmap[A, B](xs: F[A], f: A => B): F[B]
  }

The Mapper trait is parameterized by the F[_] type. F is a higher-kinded type because it takes another type parameter denoted by _. If you have to implement fmap for Vector, you’ll do something like the following:

def VectorMapper = new Mapper[Vector] {
  def fmap[A, B](xs: Vector[A], f: A => B): Vector[B] = xs map f
}

Similarly, you can define one for Option:

def OptionMapper = new Mapper[Option] {
  def fmap[A, B](r: Option[A], f: A => B): Option[B] = r map f
}

Using higher-kinded types, you can raise the abstraction level higher and define interfaces that work across various types. For instance, you can use the Mapper trait to implement fmap for the Function0 as follows:

def Function0Mapper = new Mapper[Function0] {
   def fmap[A, B](r: Function0[A], f: A => B) = new Function0[B] {
      def apply = f(r.apply)
    }
}

Function0 represents a function that doesn’t take any parameters. For example, you can use the preceding Function0Mapper to compose two functions and create a new one:

Val newFunction = Function0Mapper.fmap(() => "one",
  (s: String) => s.toUpperCase)

The newFunction.apply will result in "ONE." The first parameter defines a function that takes zero parameters and returns "one." And the second parameter defines another function that takes a String parameter and makes it uppercase. Remember that calling apply on a Function type invokes the function.

trait X {
  type E
}
type EE = X#E

scala> Either.cond(true, "one", new RuntimeException)
res4: Either[java.lang.RuntimeException,java.lang.String] = Right(one)

def fmap[A, B](r: Either[X, A], f: A => B): Either[X, B] = r match {
      case Left(a) => Left(a)
      case Right(a) => Right(f(a))
    }

def EitherMapper[X] = new Mapper[({type E[A] = Either[X, A]})#E ] {
    def fmap[A, B](r: Either[X, A], f: A => B): Either[X, B] = r match
          {
      case Left(a) => Left(a)
      case Right(a) => Right(f(a))
    }
  }

It’s a little hard to come up with generic functions like fmap on your first try. I recommend always starting with specific implementations (even if you see duplications) to understand the pattern before creating abstractions. Once you understand the pattern, higher-kinded types help to create abstractions. I encourage you to look into Scala collections^[2] to see various usages of higher-kinded types.

² Martin Odersky and Lex Spoon, “The Architecture of Scala Collections,” adapted from Programming in Scala, second edition, Odersky, Spoon and Venners, Artima Inc., 2011, http://mng.bz/Bso8.

8.2.3. Phantom types

Phantom types are types that don’t provide any constructors to create values. You only need these types during compile time to enforce constraints. It’s hard to understand their application without an example. Again, let’s consider an ordering system. An order is represented by an item and a shipping address:

case class Order(itemId: Option[Item], address: Option[String])

To place an order, you have to specify both item and shipping address. The client of the ordering system provides an item, specifies the shipping address, then places an order:

def addItem(item: String, o: Order) =
    Order (Some(item), o.shippingAddress)
def addShipping(address: String, o: Order) =
    Order (o.itemId, Some(address))
def placeOrder (o: Order) = { ... }

The problem with this approach is that the methods could get called out of order. For example, some clients could by mistake call placeOrder without specifying the shipping address. Well, you could implement necessary validations inside the placeOrder function, but using the type system to enforce an order would be even better. This is where you could use phantom types to enforce some constraints on the order object and the way it’s used by various functions. First let’s look into the following phantom types to represent states of order:

sealed trait OrderCompleted
sealed trait InCompleteOrder
sealed trait ItemProvided
sealed trait NoItem
sealed trait AddressProvided
sealed trait NoAddress

Each of these types represents a certain order state, and you’ll use them as you progress through the ordering process. When the order is first initialized, it has no item and no address, and it’s incomplete. You can easily represent that using the phantom types:

case class Order[A, B, C](itemId: Option[String],
  shippingAddress: Option[String])

def emptyOrder = Order[InCompleteOrder, NoItem, NoAddress](None, None)

The Order type now takes three type parameters, and an empty order is initialized with InCompleteOrder, NoItem, and NoAddress types. To enforce some constraints on each operation performed on the order, you’ll use combinations of these types. For example, you can only add an item to an order when it doesn’t have any items, and once an item is added its type parameter changes from NoItem to ItemProvided:

def addItem[A, B](item: String, o: Order[A, NoItem, B]) =
  o.copy[A, ItemProvided, B](itemId = Some(item))

addItem creates a new order by adding the item and changing the second type parameter from NoItem to ItemProvided. Similarly, addShipping creates a new order by updating the address:

def addShipping[A, B](address: String, o: Order[A, B, NoAddress]) =
  o.copy[A, B, AddressProvided](shippingAddress = Some(address))

To place an order, it needs to have both item and address, and you can easily verify that at compile time using types:

def placeOrder (o: Order[InCompleteOrder, ItemProvided, AddressProvided]) ={
  ...
  o.copy[OrderCompleted, ItemProvided, AddressProvided]()
}

placeOrder only accepts an order that’s complete with item and address. If you try to invoke placeOrder without an item or address, you’ll get a compile error. If I invoke placeOrder without specifying a shipping address, I get the following error:

[error]  found   :
     phantomtypes.Order[phantomtypes.InCompleteOrder,phantomtypes.ItemProvide
     d,phantomtypes.NoAddress]
[error]  required:
     phantomtypes.Order[phantomtypes.InCompleteOrder,phantomtypes.ItemProvide
     d,phantomtypes.AddressProvided]

The following listing shows the complete ordering system example with phantom types.

Listing 8.5. Ordering system with phantom types

To use this ordering system, you can create an empty order and then add the details as follows:

val o = Order.emptyOrder
val o1 = addItem("some book", o)
val o2 = addShipping("some address", o1)
placeOrder (o2)

This time you know that if the client of the ordering system doesn’t properly populate the order, it will get a compilation error. You can also use this technique to implement the type-safe Builder pattern where, using phantom types, you can ensure all the required values are populated. In the next section, you’ll use phantom types to implement type classes.

Scala isn’t limited to only these types. It comes with many more varieties than I’ve covered here. There’s a type called the method dependent type^[3] that allows you to specify the return type based on the type of the parameter, path-dependent types that allow you to constrain types by objects, and many more. My advice is to keep playing with the language, and I am sure you’ll become comfortable with Scala types.

³ “What are some compelling use cases for dependent method types?” Answered by Miles Sabin on stackoverflow, Oct 22, 2011, http://mng.bz/uCj3.

8.3. Ad hoc polymorphism with type classes

A type class is a type system construct that supports ad hoc polymorphism. Ad hoc polymorphism is a kind of polymorphism in which polymorphic functions can be applied to arguments of different types. Ad hoc polymorphism lets you add features to a type any time you want. Don’t think of type classes as classes in OOP; think of them as a category. Type classes are a way to define commonalities among sets of types. In this section you’ll learn how type classes can help in building abstractions.

8.3.1. Modeling orthogonal concerns using type classes

A simple example can demonstrate how to implement type classes in Scala. The following example implements an adapter pattern using type classes. In an object adapter pattern, the adapter (the wrapper object) contains an instance of the class it wraps. The adapter pattern is a great way to add functionality to a type through composition. Here’s the problem you’re trying to solve: you have a Movie type represented by a case class and you want to convert it to XML:

case class Movie(name: String, year: Int, rating: Double)

One quick and dirty solution could be to add a toXml method inside the case class. But in most cases that would be inappropriate because converting to XML is a completely orthogonal responsibility for the Movie class and should not be part of the Movie type.

The second solution is to use the object adapter pattern. Define a generic interface for XmlConverter and parameterize it with a type so you can use it for multiple types:

trait XmlConverter [A] {
  def toXml(a: A): String
}

And provide an object adapter for the Movie instance like the following:

object MovieXmlConverter extends XmlConverter[Movie] {
  def toXml(a: Movie) =
    <movie>
      <name>{a.name}</name>
      <year>{a.year}</year>
      <rating>{a.rating}</rating>
    </movie>.toString
}

MovieXmlConverter implements the toXml method for the Movie type. To convert an instance of Movie to XML, all you have to do from client code is the following:

val p = Movie("Inception", 2010, 10)
MovieXmlConverter.toXml(p)

The problem with the following implementation is the incidental complexity introduced by the MovieXmlConverter. The converter is hiding the object you’re dealing with, which is movie. Going to a toXml method inside the Movie class almost feels like an elegant solution. The second problem with that implementation is the rigidity of the design. It’s going to be hard to provide a separate XML converter for the Movie type. Let’s see how you can improve the solution with type classes.

The first role of a type class is to define a concept. The concept is XML conversion and could be easily represented by the XmlConverter trait:

trait XmlConverter [A] {
  def toXml(a: A): String
}

The trait is generalized for any type A. You don’t have any constraints yet. The second role of a type class is to propagate constraints automatically to a generic algorithm. For example, you can create a new method called toXml that takes an instance of a type and a converter to convert it to XML:

def toXml[A](a: A)(converter: XmlConverter [A]) = converter.toXml(a)

But this isn’t much of an improvement because you still have to create an instance of a converter and pass it to the method. What makes type classes practical in Scala is the implicit keyword. Making the converter parameter implicit allows the Scala compiler to jump in and provide the parameter when it’s missing:

def toXml[A](a: A)(implicit converter: XmlConverter[A]) =
   converter.toXml(a)

Now you can invoke toXml by passing an instance of Movie, and the Scala compiler will automatically provide the converter for you. In fact, you can pass in an instance of any type as long as you have an implicit definition of an XmlConverter that knows how to convert that type. The following listing shows the complete example.

Listing 8.6. Type class to convert a type to XML

You created a type class called XmlConverter and then provided an implicit definition of it . When using the toXml method, you have to make sure the implicit definition is available in the compiler scope, and the Scala compiler will do the rest. The flexibility of this implementation is that now if you want to provide a different XML conversion for Movie, you could do that and pass it to the toXml method as a parameter explicitly:

object MovieConverterWithoutRating extends XmlConverter [Movie] {
    def toXml(a: Movie) = <movie>
                            <name>{a.name}</name>
                            <year>{a.year}</year>
                          </movie>.toString
}
val p = Movie("Inception", 2010, 10)
toXml(p)(MovieConverterWithoutRating)

In fact, you can also make a MovieConverterWithoutRating implicit definition like the other converter. But make sure both definitions aren’t in the compiler scope at the same time—otherwise, you’ll get an “ambiguous implicit values” compile error. One way to use multiple implicit definitions for a given type is to import them in a much narrower scope, such as inside a method. The following two methods use a different XML converter for the Movie type:

def toXmlDefault(a: Movie) = {
  import Converters._
  toXml(a)
}

def toXmlSpecial[A](a: Movie) = {
  import SpecialConverters._
  toXml(a)
}

The MovieConverterWithoutRating is defined as an implicit object inside the SpecialConverter object.

Type classes are so useful that they’re used in many places across the standard library. For example, look at the sum method available for List:

def sum [B >: A] (implicit num: Numeric[B]): B

The Numeric[B] trait is nothing but a type class. Let’s see it in action:

scala> val l = List(1, 2, 3)
l: List[Int] = List(1, 2, 3)

scala> l.sum
res0: Int = 6

scala> val ll = List("a", "b", "c")
ll: List[java.lang.String] = List(a, b, c)

scala> ll.sum
<console>:9: error: could not find implicit value for parameter num:
     Numeric[java.lang.String]
              ll.sum
                 ^

The Scala library provides implicit definitions for Numeric[Int] but not for Numeric[String], and that’s why you get the implicit missing compilation error. Similarly, the following min method defined in the Scala collection library also uses Ordering[B] as a type class:

def min[B >: A](implicit cmp: Ordering[B]): A

def toXml[A: XmlConverter](a: A) =
          implicitly[XmlConverter[A]].toXml(a)

def implicitly[T](implicit e: T) = e

The common confusion about type classes is that people tend to think of them as an interface. But the key difference between an interface and a type class is that with interface your focus is on subtype polymorphism, and with a type class your focus is on parametric polymorphism. In the Java world you might know parametric polymorphism as generics, but a more appropriate name is parametric polymorphism. Another way to understand the difference is that subtyping is common in the OOP world, and parametric polymorphism is common in the functional programming world. In fact, the type-class concept is first found in the Haskell programming language, which is a purely functional language.

Type classes are a flexible way to model orthogonal concerns of an abstraction without hardwiring to the abstraction. Type classes are also useful in retroactive modeling because you can add a type class for a type anytime you want. The only limitation of type-class implementation is that everything happens statically—there’s no dynamic dispatch. The upside of this limitation is that all the implicit resolution happens during compile time, and there’s no runtime cost associated with it. Type classes have everything you need to solve the expression problem, so let’s see how.

8.3.2. Solving the expression problem using type classes

The payroll process is driven by two abstractions. One is the country for which you have to process the payroll, and the other is the payee. The USPayroll class will look something like this:

case class USPayroll[A](payees: Seq[A]) {
  def processPayroll = ...
}

The A type represents a type of payee; it could represent an employee or contractor. Similarly, the payroll class for Canada would look something like the following:

case class CanadaPayroll[A](payees: Seq[A]){
  def processPayroll = ...
}

To represent the type class for a family of payroll processors, you could define the following trait by parameterizing both country and the type of payee:

import scala.language.higherKinds
trait PayrollProcessor[C[_], A] {
  def processPayroll(payees: Seq[A]): Either[String, Throwable]
}

C is a higher-kinded type that represents a payroll type. The reason it’s a higher-kinded type is because both USPayroll and CanadaPayroll take a type parameter. And A represents the type of payee. Note that you aren’t using C anywhere except as a parameterized type, like a phantom type. It will make sense once I introduce the second building block of type class, the implicit definitions of the PayrollProcessor trait:

case class Employee(name: String, id: Long)
implicit object USPayrollProcessor
   extends PayrollProcessor[USPayroll, Employee] {

    def processPayroll(
       payees: Seq[Employee]) = Left("us employees are processed")
}

implicit object CanadaPayrollProcessor
   extends PayrollProcessor[CanadaPayroll, Employee] {

    def processPayroll(
       payees: Seq[Employee]) = Left("canada employees are processed")
}

Notice how you’re using the first type parameter of PayrollProcessor to identify the appropriate definition of PayrollProcessor based on the country. To use these implicit definitions, you could use implicit class parameters for both USPayroll and CanadaPayroll types:

case class USPayroll[A](
  payees: Seq[A])(implicit processor: PayrollProcessor[USPayroll, A]) {

    def processPayroll = processor.processPayroll(payees)
}

case class CanadaPayroll[A](
  payees: Seq[A])(implicit processor: PayrollProcessor[CanadaPayroll, A]){

    def processPayroll = processor.processPayroll(payees)
}

The preceding code snippet also demonstrates another important point: you can use implicit parameters in class definitions as well. Now when you create an instance of USPayroll or CanadaPayroll, the Scala compiler will try to provide values for implicit parameters. Here’s what you have so far.

Listing 8.7. Payroll system implemented with type class

Again, all the implicit definitions are grouped together to help you import them, as inside the RunPayroll object. Notice when you’re instantiating USPayroll that you’re providing a collection of employees, and the implicit processor will be provided by the Scala compiler. In this case, that’s USPayrollProcessor. Now assert that you also have type-safety. Create a new type called Contractor:

case class Contractor(name: String)

Because there’s no restriction on the type of payee (it’s denoted by A without any bounds), you could easily create a collection of contractors and pass it to USPayroll:

USPayroll(Vector(Contractor("a"))).processPayroll

But the moment you try to compile the preceding line, you’ll get a compilation error, because there’s no implicit definition for USPayroll and Contractor type yet. You’re still protected by the type system—it’s all good.

Note

You can annotate your type classes with @implicitnotfound to get helpful error messages when the compiler can’t find an implicit value of the annotated type.

Let’s move on with the quest of solving the expression problem using type classes. Adding a new type in the current settings is trivial; add a new class and the implicit definition of the payroll processor:

Adding a new operation to process pay for contractors is also trivial because all you have to do is provide implicit definitions of payroll processors for contractors, as in the following:

implicit object USContractorPayrollProcessor
    extends PayrollProcessor[USPayroll, Contractor] {

    def processPayroll(payees: Seq[Contractor]) =
      Left("us contractors are processed")
}

implicit object CanadaContractorPayrollProcessor
    extends PayrollProcessor[CanadaPayroll, Contractor] {

    def processPayroll(payees: Seq[Contractor]) =
      Left("canada contractors are processed")
}

implicit object JapanContractorPayrollProcessor
    extends PayrollProcessor[JapanPayroll, Contractor] {

    def processPayroll(payees: Seq[Contractor]) =
      Left("japan contractors are processed")
  }

Add the preceding implicit definitions inside the PayrollProcessorsExtension object so that you can group them all together. The following code snippet shows how to use the preceding code to process the payroll of both employees and contractors:

object RunNewPayroll {
  import PayrollSystemWithTypeclass._
  import PayrollProcessors._
  import PayrollSystemWithTypeclassExtension._
  import PayrollProcessorsExtension._

  def main(args: Array[String]): Unit = run
  def run = {
    val r1 = JapanPayroll(Vector(Employee("a", 1))).processPayroll
    val r2 = JapanPayroll(Vector(Contractor("a"))).processPayroll
  }
}

You import all the necessary classes and implicit definition and process the payroll for Japan. You again successfully solved the expression problem, this time using a functional programming technique.

If you’re a Java programmer, type classes might take a little while to get used to, but once you get comfortable with them they’ll provide the power of retroactive modeling, which in turn will allow you to respond to change quickly.

8.4. Summary

This chapter is an important milestone in understanding the various applications of Scala’s type system. Once understood and explored, Scala’s type system helps in building reusable and scalable components. And a good type system not only provides type-safety, it also provides enough abstraction to build components or libraries much more quickly. You learned about abstract type members and self-type annotation and how to build components using them. You also explored various types of types provided by Scala and saw how they can be used to build applications and create abstractions.

One of the most common ways to identify the weakness and strengths of programming languages is the expression problem. You implemented the expression problem in two different ways, clearly demonstrating the power of Scala’s type system. Scala being multiparadigm, you solved this problem using both object-oriented and functional paradigms. The object-oriented solution is implemented using abstract type members and traits. To solve this using functional programming, you learned about type classes. Type classes are a powerful way to provide polymorphic behavior at runtime, which is an important design technique for programmers. But I’ve only scratched the surface of Scala’s type system. It has more things to offer than I could possibly cover in this chapter, but I’m certain that your curiosity will entice you to explore this subject further.

The next chapter covers one of the Scala’s most popular features: actors. Scala actors make building concurrent applications easy and hassle-free.