The term “type class” has been popular for a while now, but what does it really mean? An article in Wikipedia defines a type class as an interface. This works for Java, but once we switch to Scala, it does not apply. So what is it?

In another definition in Wikipedia, type classes are defined as a tool to provide ad-hoc polymorphism. In parametric polymorphism, you define a method in a parameterized class, and it works, whatever the parameter. In ad-hoc polymorphism, however, a function is implemented differently for different types of its arguments, like 1+2 and “x”+”y”. You can read about Scala type classes in Chapter 7.3. Use type classes in *Scala in Depth*.

Let’s start with the problems that may need type classes to be properly solved.

## Problems

Case 1: calculate the sum of elements of a set. How can we do it in a generic way? For some types it’s impossible, like Date or File. So we have to delimit the type `T`

in `Set[T]`

.

Case 2: sort a list. How do we compare elements? In Java, the type must be `Comparable`

, or we need to provide a comparator. This solution is a good hint for what we are going to do.

## Solutions

Follow along in this section to see some solutions to these type class problems.

### Subtyping

The following code demonstrates how we can perform a sort:

1 2 3 4 5 |
trait Comparable[T] { def ≤(other: T): Boolean } trait StringOrder extends Comparable[String] { ... } class String extends StringOrder |

Now we can sort strings. But then we have to extend an existing class, so how can we provide a locale-specific order? How do we know if `"año" ≤ "ave"`

?

### Structural Types

As another case, suppose we only want to calculate the total size of containers; each one has method `size()`

:

1 |
totalSize(1::5::Nil, Set("x", "y", "z"), "Hello") |

The Scala-specific solution to specify that a class has a `size`

method looks like this:

1 2 |
def totalSize(containers: {def size: Int}*) = (0/:containers)(_+_.size) |

Here, we require that a container the function accepts must have an `Int`

-valued method `size`

.

Now we have more freedom, with no need to inherit. The problem is that if sizes are named differently for different types, we are out of luck. Some of them are called `length`

.

### “Pimp My Library” Pattern

We use implicits to produce an instance of a richer class, given an instance of a poorer class, like in this example:

1 2 3 4 5 |
trait Comparable[T] { def ≤(other: T): Boolean } trait NaturalOrder extends Comparable[Being] { ... } implicit def order(b:Being): NaturalOrder = new NaturalOrder {...} |

`Being`

is not `Comparable`

; but when `≤`

is called on its instance, the compiler provides a call of the `order`

method, which creates a new instance of `NaturalOrder`

that participates in the operation of comparison.

There are, however, a couple of caveats. How exactly do we compare “`año`

” and “`ave`

“? What if the operation involves two types (like in multiplying a matrix by a scalar)?

### A Better Solution

To show it, I’ll start with the “Pimp My Library” pattern, and refactor it to type class. Say, we have:

1 2 3 4 5 6 7 8 9 10 |
trait Comparable[T] { def ≤(other: T): Boolean } object SpanishStrings { val coll = Collator.getInstance(new Locale("ES")) def compare(a: String, b: String) = coll.compare(a,b)<0 } implicit def order(a:String) = new Comparable[String] { def ≤(b: String) = SpanishStrings.compare(a, b) } |

The object `SpanishStrings`

encapsulates collation order, and I use this object to do the comparison.

A type class pattern looks like the following:

1 2 3 4 5 6 7 8 9 10 11 12 |
trait CanCompare[T] { def compare(a:T, b:T): Boolean } trait Comparable[T] { def ≤(other: T): Boolean } implicit object SpanishStrings extends CanCompare[String] { val collator = Collator.getInstance(new Locale("ES")) def compare(a: String, b: String) = collator.compare(a,b)<=0 } implicit def order(a:T)(implicit c: CanCompare[T]) = { new Comparable[T] { def ≤(b: T) = c.compare(a, b) } } |

Now our comparator object implements a trait, and is implicitly present in an `order`

function. It is the compiler’s responsibility to find an appropriate witness object (`SpanishStrings`

, in our case). That’s all we need; but we rewrite it in the “type class pattern” way:

1 2 3 4 |
implicit def order[T:CanCompare](a:T) = new Comparable[T] { def ≤(b: T) = implicitly[CanCompare[T]].compare(a, b) } |

The expression, `[T:CanCompare]`

is a syntactic sugar; it says “find a witness object implementing `CanCompare[T]`

”.

This is how type class looks in Scala, but what exactly is that.

## What Exactly is Type Class?

A type class is just a class of types; a subclass of the class of all types. How can we specify a certain class of types?

- Trait (interface):
`a class Record extends Serializable`

.

Here we are saying that type Record belongs to a class of types that extends`Serializable`

. - Parameterized type, e.g.
`List[_]`

, is a type that belongs to this class is any`List`

, parameterized by a list element type:`List[String], List[Int], List[List[Set[Date]]]`

. - type class pattern, for example
`def sum[M: Monoid](coll: Seq[M]) {...}`

provides a witness object that ensures the functionality we need. In this sense it is, yes, a mechanism for ad-hoc polymorphism.## An Inspiring Example

For this example we look at java.util.ArrayList as a Functor (a type of mapping between categories). Read about functors in Chapter 11.2. Functors and monads, and how they relate to categories. Let’s now look at what a Functor is by looking here:

123trait Functor[F[_]] {def map[X,Y](f: X => Y): F[X] => F[Y]}Here’s what this says: a type F is a functor when there is a method map transforming functions X-> Y into functions F[X]->F[Y]. Collections in Scala have a map method, but

`java.util.ArrayList`

does not. Type classes will help:1234567implicit object JAL_a_Functor extends Functor[ArrayList] {def map[X,Y](f: X => Y) = (xs: ArrayList[X]) => {val ys = new ArrayList[Y]for (i <- 0 until xs.size) ys.add(f(xs.get(i)))ys}}This is our witness object for

`ArrayList`

. Now build a transformer:1234implicit def fops[F[_]: Functor, A](fa: F[A]) = new {val witness = implicitly[Functor[F]]final def map[B](f:A=>B):F[B] = witness.map(f)(fa)}The method requires that F belongs to a

`Functor`

type class. Then it takes an instance of`F[A]`

for a given`A`

, and returns an instance that has`map()`

, so it is a functor.Here’s what this can produce:

123val testList = new ArrayList(Arrays.asList("this", "is", "a", "test"))val transformed = testList.map(_.toUpperCase)We will have

`ArrayList("THIS", "IS, "A", "TEST")`

. So, unlike Java, we do not need to use the transformation chains; the compiler can provide all of the transformations needed, and, if necessary, we can specify which ones to use.My hope is that with this blog post the topic of Scala type classes is clearer to you.

## Safari Books Online has the content you need

Check out these Scala books available from Safari Books Online:

Scala in Action is a comprehensive tutorial that introduces Scala through clear explanations and numerous hands-on examples. Because Scala is a rich and deep language, it can be daunting to absorb all the new concepts at once. This book takes a “how-to” approach, explaining language concepts as you explore familiar programming challenges that you face in your day-to-day work. This book takes a step-by-step tutorial approach to teaching you Scala. Starting with the fundamental elements of the language, Programming in Scala introduces functional programming from the practitioner’s perspective, and describes advanced language features that can make you a better, more productive developer. Scala in Depth is a unique new book designed to help you integrate Scala effectively into your development process. By presenting the emerging best practices and designs from the Scala community, it guides you though dozens of powerful techniques example by example. ### About the author

Vlad Patryshev was born in Russia, and has an education in Math (including now popular category theory). Since 1998 in the US, he worked at Borland (JBuilder team), then at Google in various teams, and had a 20% project, an onscreen keyboard, now available on various Google pages. He then changed several Bay Area startups, and now is working at HealthExpense.com. A functional programmer and a Scala fan since 2008, he is now an organizer of Scala BASE and Bay Area Categories and Types meetups. As a hobby, he rides his road bike, builds decks, and drives around the US (Key West to the Polar Circle in Alaska). He can be reached at @vpatryshev.