Thursday, June 17, 2010

Implicit tricks -- the Type Class pattern

Some people have been recently discovering the Scala equivalent of Haskell's Type Classes. I was a bit suprised because I thought everyone with enough Scala experience already knew about them, but, apparently, I was wrong.

A type class is basically a way to classify types based on the methods they offer. It offers an alternative to inheritance, in that you can group many different classes (types) that share a common set of methods, just like a superclass can be used to group its subclasses.

While Scala does not support type classes directly, the same patterns that hold true for Haskell can be simulated by using implicits in Scala. Perhaps a bit improperly, Scala programmers have been calling this pattern "type classes" as well.

It will feature proeminently in Scala 2.8, where examples can be found with Numeric, Ordering and even, I think, CanBuildFrom. In fact, one can find many questions on Stack Overflow related to Numeric being used precisely as a type class.

So, let me give a simple example of the kind of usage this can be put to. This is something someone just asked me on the #Scala channel on IRC, and I decided it makes for a nice example.

The problem put to me was restricting the options of a type parameter T without resorting to inheritance. For instance, if I want a method to work for Long and Int, but not any other type, there is no way to express that through a superclass. But the type class pattern can be used to solve it!

Here is the idea: I'll create an abstract class that will represent my type class. I'll then create elements representing the classes belonging to that type class. Finally, I'll use an implicit parameter to restrict my type parameter to that type class.

First, my abstract class:

abstract class Acceptable[T]

Yes, that's it. Not much to it, is there? Well, most often I would add to that class the methods I wish that type class to have. For instance, Numeric have all the normal operators you'd expect from classes that represent numbers. In this case, however, that won't be necessary, so I'm keeping it simple.

Next, let me create the members of my type class. I wish to create two of them: one for Int, and another for Long. To make them available without need for any import statements, I'll put them inside the companion class to Acceptable. Also, note that they are implicits.

object Acceptable {
implicit object IntOk extends Acceptable[Int]
implicit object LongOk extends Acceptable[Long]
}

Little to it, right? So, how do I get to use it? Well, let's create a simple method that will only accept Int and Long, as we wanted:

def f[T: Acceptable](t: T) = t

That weird declaration of T is called a context bound in Scala lingo. It's new to Scala 2.8, precisely to make this stuff easier. What it actually does is automatically define an implicit parameter -- and, for that very reason, it cannot be combined with other implicit parameters, though you can always use the full syntax to get the same result. Here's the full syntax:

def f[T](t: T)(implicit ev: Acceptable[T]) = t

So, does it work? Well, here is a small session using it:

scala> f(1)
res0: Int = 1

scala> f(1L)
res1: Long = 1

scala> f(1.0)
<console>:8: error: could not find implicit value for parameter ev: Acceptable[Double]
f(1.0)
^

scala> f(1: Byte)
<console>:8: error: could not find implicit value for parameter ev: Acceptable[Byte]
f(1: Byte)
^

Now, to those of you who may think this is neat but of little use, I'll point you to two examples of its usage in the new collections: the methods sum and max. If you try to call sum on a list of things that are not Numeric, it won't work -- at compile time. Likewise, if you try max on a list of things for which there are no Ordering available, it won't compile either. This way, these methods could be safely added to the collections without resorting to throwing exceptions at run-time!

This is just little window into what is possible -- enough to get a hang on the pattern without risking information overload. But look around, as there is much more to it!

10 comments:

  1. Concise post. Packed with power. Excellent.

    Thank you, Daniel.

    ReplyDelete
  2. Hi,

    interesting article!
    I tried to implement a method average like those sum, max or min methods. But unluckily there is a plus, a minus and a times method. But no divide method. Is there a reason this was done that way?

    ReplyDelete
  3. The method div is available on Numeric's subclass Fractional, while Numeric's subclass Integral offers quot and rem.

    ReplyDelete
  4. Odd. Running this example on 2.8final doesn't work for me. I get:
    scala> f(99)
    :8: error: could not find implicit value for evidence parameter of type Acceptable[Int]f(99)

    However, if I remove the companion object and just declare the implicit objects inline, everything's dandy. Any idea why?

    ReplyDelete
  5. Jakob, you probably pasted those lines directly into REPL, right? If that's the case, what happened is that the object as not recognized as a companion object, as it was placed in a different package -- a consequence of the way REPL works.

    You may try typing "abstract class Acceptable[T]; object Acceptable {", etc, to avoid this.

    ReplyDelete
  6. Great post! I was searching for a good explanation for type classes: after reading several articles, didn't get it until I read your post ;)

    After rethinking it, a question came up: you say "A type class is basically a way to classify types based on the methods they offer. It offers an alternative to inheritance, in that you can group many different classes (types) that share a common set of methods, just like a superclass can be used to group its subclasses."

    Isn't that what duck typing was made for? If not, what additional benefit do type classes offer?

    ReplyDelete
  7. @sieber It isn't really like duck typing. First, duck typing doesn't add methods to existing types, which both inheritance and type classes do. Monkey patching does that as well, as do some other techniques. Second, and most important of all, type classes gives you type safety, which duck typing takes away.

    ReplyDelete
  8. Great concise post Thanks Daniel!

    ReplyDelete