Type Classes and Bounds in Scala

I've been doing some initial experiments with the Scalaz library (https://github.com/scalaz/). This is a great extension to the Scala standard library that adds a wide range of functional programming concepts to the language. Many of its features are based around the concept of Type Classes.

The type class concept originally comes from Haskell, and provides a way to define that a particular type supports a certain behavioural concept without the type having to explicitly know about it. For example, a type class may define a generic 'Ordered' contract and implementations can be defined for different types separate from the definition of those types. Any type that has an implementation of the 'Ordered' type class can then be used in any functions that work with ordering.

The Scala language provides a way to support type classes via its implicit mechanism. In order to get my head around this fully I created some examples to experiment with how this works. Now I fully grasp the mechanisms, the Scalaz library makes much more sense. I therefore thought I'd share my experiment in case it proves useful to anyone and as an aide-mémoire to myself for the future.

In addition, my examples also make use of the different type bounds mechanisms provided by Scala, so I will demonstrate these in my examples as well.

The full source code can be found in the following gist: https://gist.github.com/1247752.

Without Type Classes

In the first example, I built a simple solution that doesn't make any use of the type class concept. This solution is much like you would implement in Java, with an interface defining the behaviour and classes that implement this interface:

trait Publishable {  
  def asWebMarkup: String
}

case class BlogPost(title: String, text: String) extends Publishable {
  def asWebMarkup =
    """|
%s
       |
%s
""".stripMargin format(title, text)
}

Here we have a trait Publishable that indicates that something can represent itself as a web markup string. Then we have a case class that implements the trait and provides the method to return the markup. Next, we declare a class that can do the publishing:

class WebPublisher[T <: Publishable] {
  def publish(p: T) = println(p.asWebMarkup)
}

Note that we have defined this as a templates class and that we have used the <: bounds notation to require that our type T is only valid if it extends the Publishable trait. All we need to do now is use it:

val post = new BlogPost("Test", "This is a test post")
val web = new WebPublisher[BlogPost]()
web publish(post)

Ok, so that works fine. However, what happens when we either can't or don't want BlogPost to implement the Publishable trait? There can be many reasons for this: perhaps we don't have the BlogPost domain object source; perhaps the object is already quite complex and we don't want to pollute it with publishing knowledge; perhaps it's shared by multiple teams or projects and only ours needs publishing knowledge. So, what do we do?

Without type classes there are some options: we might extends the domain class to implement the trait; we might create a wrapper class or we might create a helper utility. However, all of these result in a level of indirection and complication in our code. Let me explain...

If we internalise the knowledge of the wrapper/helper/sub-class in our publishing code we end up with some horrific type matching:

class WebPublisher {
  def publish(p: AnyRef) = p match {
    case blogPost: BlogPost => BlogPostPublishHelper.publish(blogPost)
    case _ => …
  }
}

However, if we externalise the knowledge of publishing then our client code has to do the conversion:

class WebPublisher {
  def publish(p: Publishable) = ...
}

web publish(new PublishableBlogPostWrapper(blogPost))

Clearly, both solutions lead to fragile boilerplate code that pollutes our main application logic. Type classes provide a mechanism for isolating and reducing this boilerplate so that it is largely invisible to both sides of the contract.

Type Classes with Implicit Views

Fortunately, Scala provides a mechanism whereby we can declare an implicit conversion between our BlogPost and a Publishable version of our instance. So, let's start with the simple stuff:

trait Publishable {
  def asWebMarkup: String
}

case class BlogPost(title: String, text: String) 

So, we now have a blog post that doesn't implement the Publishable trait. Let's now define the conversion that can implicitly turn our blog post into something that supports publishing (we would typically add this into our publishing code rather than the domain object in order to isolate all knowledge of Publishable to just the area that needs it):

implicit def BlogPostToPublishable(blogPost: BlogPost) = new Publishable {
  def asWebMarkup =
    """|
%s
       |
%s
""".stripMargin format(blogPost title, blogPost text)
}

Our conversion just creates a new Publishable instance that wraps our blog post and implements the required methods. But, how do we make use of this? We have to change our web publisher very slightly:

class WebPublisher[T <% Publishable] {  
  def publish(p: T) = println(p.asWebMarkup)
}

All we have in fact changed is the <: bounds to a <% bounds. This new one is called a view bounds and defines that we can instantiate a WebPublisher with type T only if there is a view (in this case as implicit conversion) in scope from T to Publishable.

Our code to call this remains the same:

val post = new BlogPost("Test", "This is a test post")
val web = new WebPublisher[BlogPost]()
web publish(post)

Fantastic, our publish code gets objects that it knows are publishable, while our client code can just pass domain objects. We have all the boilerplate for conversion separated out from the main code.

However, while this all seems good, this approach does have its downsides. As you can see we are using the wrapper approach: creating a new instance of a Publishable class that wraps the original object. In a high volume system, the additional object allocations of new Publishable wrapper instances on each call to the publish method may have some less than ideal memory and garbage collection impacts.

The other problem with this approach is that is reduces our ability to compose methods in interesting ways. The reason for this is that once the publishing code has actually invoked the implicit conversion it now has the Publishable wrapper rather than the original object. If it passes this Publishable to other methods or classes than these are not aware of the original wrapped type or instance.

We can overcome this problem by modifying the Publishable trait to have a generic parameter type and support a get method to extract the wrapped value - but this then should really be called PublishableWrapper and some of the simplicity starts to break down.

I think the root of the problem here is that type classes are a very functional concept and implicit views tries to coerce these into a hybrid object/functional world. Fortunately, as of Scala 2.8 there is an additional way to implement the type class approach that leads to a more functional style of coding...

Type Classes with Implicit Contexts

An alternative to implicitly converting one class to a wrapper version of that class that adds additional behaviour is to follow more of a helper like approach. In this model we provide an implicit evidence parameter that implements the type class specific behaviour. This is a much more functional approach in that we don't alter the type we are working on. So, on with the code...

trait Publishable[T] {     
  def asWebMarkup(p: T): String
}

case class BlogPost(title: String, text: String)

This is our new Publishable trait and BlogPost class. Note that our Publishable is no longer intended to be implemented or used as a wrapper. Instead, it is now a contract definition of functional behaviour that takes a parameter of type T and transforms it into a String. A much cleaner abstraction. In fact, we can even create a single object instance that implements this behaviour for blog posts:

object BlogPostPublisher extends Publishable[BlogPost] {     
  def asWebMarkup(p: BlogPost) =
     """|
%s
        |
%s
""".stripMargin format(p title, p text)
}

We are also going to need our implicit. This time however, rather than being a conversion it becomes an evidence that we have something that implements Publishable for the type BlogPost:

implicit def Publishable[BlogPost] = BlogPostPublisher 

We also need to update our WebPublisher a bit:

class WebPublisher[T: Publishable] {  
  def publish(p: T) = println(implicitly[Publishable[T]] asWebMarkup(p))
}

There are two interesting things about this class. First, the bounds has now switched from view (<%) to context (:). The context bounds effectively modifies the class declaration to be:

class WebPublisher[T](implicit evidence$1: Publishable[T]) {  ...
}

The second change is the use of implicitly[Publishable[T]] which is a convenience for getting the implicit evidence of the correct type so that you can call methods on it.

Our code to call this remains exactly the same:

val post = new BlogPost("Test", "This is a test post")
val web = new WebPublisher[BlogPost]()
web publish(post)

One advantage that should be immediately obvious is that we are no longer creating new instances for each implicit use. Instead, we are using the implicit evident parameter (which is in this case an object) and passing our instance to it. This is more efficient in terms of allocations.

Also, we explicitly show where we make use of the implicit evidence, which is clearer. This also means that we are never creating a new wrapped type of T that we pass on to other code. We always pass on instances of type T that have implicit evidence parameters that allow T to behave as a particular type class instance.

Conclusion

We have looked at two different approaches to solving the problem of adding behaviour to an existing class without requiring it to explicitly implement a particular contract or extend a specific base class. Both of these make use of Scala implicits and type classes.

Implicit conversions with view bounds provides an approach where a type T can be converted into the type required by the type class. This works, but there are issues associated with the wrapping or transformation aspects of the conversion.

Implicit evidence parameters within context bounds overcome these problems and provide a far more functional approach to solving the same problem.