Dedicated to the 1987 album:

Table of Contents

• What are type classes?
• Why would I want them?
• When should I use them?
• How can I implement them?

What are type classes?

Type classes were introduced by Haskell (via [1]) to support ad-hoc polymorphic functions.

Ad-hoc polymorphism refers to functions which accept different types and can act differently based the argument's type. Also called function (or operator) overloading.

[1] "How to make ad-hoc polymorphism less ad-hoc"

Why do I need type classes?

Is ad-hoc polymorphism hard?

Can inheritance solve this problem?

OO languages can (often) support ad-hoc polymorphism via inheritance.

case class Sound(hz:Int)
trait Ringer { def ring: Sound }

object Phone extends Ringer { def ring = Sound(1100) }
object Bell extends Ringer { def ring = Sound(400) }
    

Can inheritance solve this problem?

Yes, kind of...

But you'll often hit brittle classes, or repeatedly refactor your object hierarchies.

TODO: brittle inheritance nightmare goes here.

Can reflection solve this problem?

Probably. Reflection is a quick-and-dirty way to get the job done.

case class Sound(hz:Int)

def ring(thing:Any) = thing match {
  case Phone => Sound(1100)
  case Bell => Sound(400)
  case _ => error("can't ring")
}
    

Can reflection solve this problem?

Reflection "works", except when it doesn't:

java.lang.RuntimeException: can't ring
        at scala.sys.package$.error(package.scala:27)
        at scala.Predef$.error(Predef.scala:66)
        at .(:8)
        at .()
        at .(:11)
        at .()
        at $print()
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
        at java.lang.reflect.Method.invoke(Method.java:597)
        at scala.tools.nsc.interpreter.IMain$ReadEvalPrint.call(IMain.scala:704)
        at scala.tools.nsc.interpreter.IMain$Request$$anonfun$14.apply(IMain.scala:920)
        at scala.tools.nsc.interpreter.Line$$anonfun$1.apply$mcV$sp(Line.scala:43)
        at scala.tools.nsc.io.package$$anon$2.run(package.scala:25)
        at java.lang.Thread.run(Thread.java:662)
    

Q: Is ad-hoc polymorphism hard?

A: Hard to get right without tightly coupling the polymorphism to either:

• interface (as in reflection example with ring())
• member types (as in Bell and Phone with inheritance)

In some cases this is fine, but especially when using interfaces and types that the author doesn't control, these couplings cause structural problems.

So how do type classes avoid tight coupling to interface or member types?

So how do type classes avoid tight coupling to interface or member types?

By introducing a third thing: type class instances!

So how do type classes avoid tight coupling to interface or member types?

1. (In this case the "interface" is a type class.)
2. Create an instance of the type class for each member type.
3. Each instance "glues" a member type to the type class interface.
4. Each instance implements the type class in terms of the member.
5. Neither the type class nor the member type know about the instance.

TL;DR: Glue!!!

1. The big idea is that there are "glue instances".
2. Instances of a type class are distinct from the type class and the member type.
3. When you use a type class, you're using the "glue instance" and not the member type!

Example in Haskell

class Eq a where
  (==), (/=) :: a -> a -> Bool
  x /= y = not (x == y)

instance Eq Integer where
  x == y = x `integerEq` y

instance Eq Float where
  x == y = x `floatEq` y
    

Example in Java

interface Eq<T> {
  public bool eq(T x, T y)
  public bool neq(T x, T y) { return !eq(x, y) }
}

class IntegerHasEq implements Eq<Integer> {
  private static final IntegerHasEq i = new IntegerHasEq();
  public static IntegerHasEq getInstance() { return i; }
  public bool eq(Integer a, Integer b) {
    return a.intValue() == b.intValue();
  }
}

class FloatHasEq implements Eq<Float> {
  private static final FloatHasEq i = new FloatHasEq();
  public static FloatHasEq getInstance() { return i; }
  public bool eq(Float a, Float b) {
    return a.floatValue() == b.floatValue();
  }
}
    

So there it is, we're done.

So there it is, we're done.

What, you don't like the Java version?

You haven't even seen it in use yet!

So there it is, we're done.

What, you don't like the Java version?

You haven't even seen it in use yet!

OK, seriously...

Example in Scala

trait Eq[A] {
  def eq(a:A, b:A):Bool
  def neq(a:A, b:A):Bool = !eq(a, b)
}

object IntHasEq extends Eq[Int] {
  def eq(a:Int, b:Int) = a == b
}

object FloatHasEq extends Eq[Float] {
  def eq(a:Float, b:Float) = a == b
}
    

There's a lot more. But this is the main part:

1. A trait parameterized on A with some methods.
2. Some objects/values that extend the trait for member types.

The trait is the type class; the objects are the "glue instances".

Wait there's more?

Since type classes aren't built into Scala (unlike Haskell) the previous definition doesn't give you everything you want:

1. You'd have to pass glue instances manually.
2. You could't call methods on A but only on glue instances.
3. There's no obvious signal that type classes are being used.

So how do we make type classes in Scala nicer?

So how do we make type classes in Scala nicer?

1. Implicits

So how do we make type classes in Scala nicer?

1. Implicits
2. ...

So how do we make type classes in Scala nicer?

1. Implicits
2. Pretty much just implicits

So how do we make type classes in Scala nicer?

1. Implicits
2. Pretty much just implicits
3. That is: implicit values, parameters, and conversions

Why do we have to fuss with implicits?

Because Haskell's scoping is so simple, and because Scala is OO.

Type classes aren't built-in to the language (yet)

Sorry.

Use implicit parameters to functions

Instead of explicitly passing glue instances, pick them up magically:

// this is the sugary version
def bar[T:Numeric](a:T, b:T) = ...

// this is the same thing, but more explicit
def foo[T](a:T, b:T)(implicit n:Numeric[T]) = ...
   

Make implicits available to search

Stash implicit values in the companion, or somewhere they can be imported from:

object Eq {
  ...

  implicit object IntHasEq extends Eq[Int] { ... }
  implicit object FloatHasEq extents Eq[Float] { ... }
}
   

Create implicit decorators to add operators/methods

// this is the decorator which will add methods/operators to T
class EqOps[T](lhs:T)(implicit e:Eq[T]) {
  def ===(rhs:T) = e.eq(lhs, rhs)
  def !==(rhs:T) = e.neq(lhs, rhs)
}

// this is the "old" way to add operators to T...
trait Eq[T] {
  ...
  implicit def mkOps(lhs:T) = new EqOps(lhs)
}

// and this is the "new" way to do it
object Implicits {
  implicit def infixOps[T:Eq](lhs:T) = new EqOps(lhs)
}
   

Let's see it all together...

trait Eq[A] {
  def eq(a:A, b:A):Bool
  def neq(a:A, b:A):Bool = !eq(a, b)
  implicit def mkOps(lhs:T) = new EqOps(lhs)
}

object ExtraImplicits {
  implicit def infixOps[T:Eq](lhs:T) = new EqOps(lhs)
}

class EqOps[T](lhs:T)(implicit e:Eq[T]) {
  def ===(rhs:T) = e.eq(lhs, rhs)
  def !==(rhs:T) = e.neq(lhs, rhs)

}

object IntHasEq extends Eq[Int] {
  def eq(a:Int, b:Int) = a == b
}

object Eq {
  implicit val intHasEq = IntHasEq
}
   

Advantage over Haskell

Interestingly, Scala's type classes have (at least) one advantage:

Haskell can only use one glue instance at a time, but Scala can use many.

Useful for Ordering[Complex], etc.

What are some examples of type classes in Scala?

1. Ordering
2. Numeric (which I work on)
3. other libraries (e.g. Scalaz) use this pattern heavily

You fraud! Ordering.scala looks totally different!

That isn't a question.

But seriously, there isn't a "standard" type class pattern (yet).

Different strategies have different weaknesses/strengths.

Adding the implicit operators to T requires imports

Right now, there are two ways to do this:

// new: imports all lower-priority implicit conversions
import my.pkg.ExtraImplicits._
def foo[T:Eq](a:T, b:T) = a == b

def bar[T](a:T, b:T)(implicit e:Eq[T]) = {
  // old: import glue instance's own implicit conversion
  import e.mkOps
  a == b
}
    

Adding the implicit operators to T requires imports

1. New way is nicer syntactically
2. Old way uses fewer, tighter implicits
3. Would be nice if the imports could be eliminated
4. Ambiguous implicit problems...

Ambiguous implicit problems?

class Animal { ... }
class Person extends Animal { ... }

trait Edible[T] { ... }
def eat[T:Edible](t:T) = ...
object Edible {
  implicit object AnimalIsEdible extends Edible[Animal]
  implicit object PersonIsEdible extends Edible[Person]
}

val bob = new Person()
eat(bob) // BOOM! ambiguous implicits
    

Ambiguous implicit problems?

You can (sometimes) fix this by making the trait contravariant:

trait Edible[-T] { ... }
def eat[T:Edible](t:T) = ...
object Edible {
  implicit object AnimalIsEdible extends Edible[Animal]
}

val bob = new Person()
eat(bob) // ok, if you think cannibalism is fine
    

Other problems:

1. Baking implicits into companion creates coupling
2. Performance?
3. Layout/inner classes/scoping uncertainty
4. Type class inheritance?

Despite these issues, type classes are great!

1. Great for serialization/deserialization!
2. Use with @specialized to avoid boxing
3. Great for working with other people's weird interfaces
4. Implicit conversion's older sibling.

the end