Posted by & filed under Content - Highlights and Reviews, Programming & Development.

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:

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():

The Scala-specific solution to specify that a class has a size method looks like this:

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:

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:

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

A type class pattern looks like the following:

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:

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:

    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:

    This is our witness object for ArrayList. Now build a transformer:

    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:

    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.

Tags: Functor, java, refactor, Scala, subtyping, Type Classes,

Comments are closed.