Mastering FP and OO with Scala

Making use of functional and object-oriented programming on JVM

Ad Hoc Polymorphism in Scala With Type Classes

| Comments

My journey into the depths of Scala is in full swing. Not only can I learn the theory (with the group of Warsaw Scala Enthusiasts), but also apply it to commercial projects (with the Scala development teams of DeepSense.io and HCore). Each day I feel I’m getting better at using type system in Scala in a more concious and (hopefully) efficient manner.

This time I sank into type classes that is a means of doing ad hoc polymorphism in Scala.

From ad hoc polymorphism article on Wikipedia:

In programming languages, ad hoc polymorphism is a kind of polymorphism in which polymorphic functions can be applied to arguments of different types, because a polymorphic function can denote a number of distinct and potentially heterogeneous implementations depending on the type of argument(s) to which it is applied.

The blog post presents a way to implement the type classes concept in Scala.

p.s. I’m yet to find out how much of it is multimethods in Clojure (that was once of much help to introduce me to functional programming).

Theory

From the article Polymorphism (computer science)) on Wikipedia, you can read about three different kinds of polymorphism:

  • subtyping
  • parametric polymorphism
  • ad hoc polymorphism

The order does matter (and is different from the Wikipedia article’s one) as I think that’s exactly the order of when and how well developers master them (in any programming language).

I reckon the Scala community finds the first two quite often used in code that contributes to how well it’s understood and applied (except variance), and just the last one - ad hoc polymorphism - is proving a major hurdle for many, me including. It didn’t click for me for a long time, either, only until I found the “venues” of very concise and comprehensible material (see References section below).

In programming languages and type theory, polymorphism is the provision of a single interface to entities of different types.

The difference between subtyping and parametric polymorphism and ad hoc polymorphism is that the type hierarchy is expressed explicitly using extends keyword in Scala (for subtyping) or type parameters (for parametric polymorphism) while ad hoc polymorphism bases itself on implicit classes to mixin the behaviour (using traits). And that’s pretty much all, technically.

Let’s see it in a Scala code.

Practice

Algebraic data types (raw data)

Let’s assume you have the following type hierarchy (from Tutorial: Typeclasses in Scala with Dan Rosen):

sealed trait Expression
case class Number(value: Int) extends Expression
case class Plus(lhs: Expression, rhs: Expression) extends Expression
case class Minus(lhs: Expression, rhs: Expression) extends Expression

No behaviour, but algebraic data types or (often called) raw data.

Think about how you’d go about evaluating expressions, i.e. Plus(Minus(Number(5), Number(3)), Number(18)), i.e. how to make the following application compile and print 20?

object Main extends App {
  val expr = Plus(Minus(Number(5), Number(3)), Number(18))
  println(...) // do something with expr so it prints 20
}

The past me would change sealed trait Expression to include def value: Int and force the three case classes Number, Plus and Minus follow. I’d not be surprised if you thought exactly so. You should not, however.

Think about the case where you must not change them as they could be provided as a library or be part of the language or be licensed or…I simply ask you not to.

objects to apply behaviour

Since you’re in Scala, you could easily work it around with an object, say object ExpressionEvaluator, that would pattern match to types and do the heavy lifting, i.e. know what to do with each and every type:

object ExpressionEvaluator {
  def value(expression: Expression): Int = expression match {
    case Number(value) => value
    case Plus(lhs, rhs) => value(lhs) + value(rhs)
    case Minus(lhs, rhs) => value(lhs) - value(rhs)
  }
}

That’s quite inefficient and cumbersome, though. You’d have to know about all of the implementations as well as about what to do for each. It’s nearly impossible to have right, complete and still flexible.

With the above object, you’d write:

object Main extends App {
  val expr = Plus(Minus(Number(5), Number(3)), Number(18))
  println(ExpressionEvaluator.value(expr)) // print the value
}

implicits in Scala

Let’s do it the right way, so it’s not ExpressionEvaluator to know what to do with every Expression, but expressions themselves do what they’re supposed to do instead.

You may have heard about implicits in Scala. Perhaps, you may have used them, too. Think about a solution with implicit machinery so the following is possible:

object Main extends App {
  val expr = Plus(Minus(Number(5), Number(3)), Number(18))
  println(expr.value) // print the value
}

One way in Scala would be to apply Pimp my Library pattern leveraging implicit classes to add necessary methods as follows:

implicit class ExpressionOps(e: Expression) {
  def value = ... // calculate the value
}

And have a implicit class per case class and sealed trait Expression, too. The reason to have the implicits is to add a value method to every type, i.e. implicitly convert types without value to ones that have it.

implicit class ExpressionOps(e: Expression) {
  def value: Int = e match {
    case n : Number => n.value
    case p : Plus => p.value
    case m : Minus => m.value
  }
}

implicit class PlusOps(p: Plus) {
  def value: Int = p.lhs.value + p.rhs.value
}

implicit class MinusOps(m: Minus) {
  def value: Int = m.lhs.value - m.rhs.value
}

Note that since Number had value already, an implicit was not needed.

With the implicits in place, you can write:

println(expr.value)  // prints 20

The implicit-based solution is far much more flexible because calculating a value is the responsibility of an implicit in scope – a change in a single implicit, say MinusOps, would only change how Minus.value works (with no changes to the rest of the “framework”).

You’re halfway to typeclasses!

Partial ad hoc polymorphism

Think about the case where you’d have a library to calculate a value of Valueable values (no pun intended). Say, you have such a library that offers the following “calculator”:

def calculate(v: Valueable) = ... // calculate the value of v

How would you go about converting Expressions to Valueables so a value of Expression type would participate in the contract of def calculate?

You’re right that whenever type conversion is needed in Scala, implicits have their say – you used them already to have def value for Expression type hierarchy. You’re going to use them again with a very small change that has enormous impact. Doing so will introduce the type class design pattern.

The current solution relies on values with def value – it’s like having a library that uses structural typing in Scala that unfortunatelly uses reflection and hence is very costly performance-wise. Happily, you don’t need structural types.

If you had a library that expects values of some type, say trait Valueable, to calculate a value or some other library to JSONify them (using some trait Json), the previous solutions would fall short – you’ve merely met the requirement of being able to call a value method on values, but the values don’t belong to a single type hierarchy of some trait Valueable that the library uses.

Assume you have a library that works with trait Valueable-only values and there’s a calculate method to work with them as follows:

trait Valueable {
  def value: Int
}

def calculate(v: Valueable) = v.value

Note that the library knows nothing about the Expression type hierarchy. The Expression type hierarchy could not even have existed at the time Valueable did.

A more flexible and efficient solution is to somehow meld the Expression type hierarchy with Valueable and create is-a relationship. No, no, you’re not going to change the Expression trait in any way. You must not and you even can’t, remember?

Welcome to typeclasses (also known as type class design pattern)!

In order to have extends-like semantic at runtime with no extends Valueable in the (closed and sealed) Expression type hierarchy you change implicit classes to have the common trait mixed in, instead.

implicit class ExpressionOps(e: Expression) extends Valueable {
  def value = e match {
    case n: Number => n.value
    case p: Plus => p.value
    case m: Minus => m.value
  }
}

implicit class PlusOps(p: Plus) {
  def value: Int = p.lhs.value + p.rhs.value
}

implicit class MinusOps(m: Minus) {
  def value: Int = m.lhs.value - m.rhs.value
}

With the above implicit classes that all extends Valueable, you can safely do expr.value for any Expression value for which an implicit exists in scope and be done with the task at hand. Notice how Scala “executes” value on the different types (that’s based upon using implicit classes for the types when value is needed).

println(calculate(expr))  // prints 20

For what is worth, the calculate method belongs to a library that knows nothing about Expression type and you can’t change it so Expressions would be worked with. That’s exactly where typeclasses shines and are hard to beat.

This is the version of type classes pattern as described in the book Programming Scala, 2nd Edition in “Type Class Pattern” section, page 156.

Final solution: Value[T] type class

You can still do better than that in Scala and that’s what (the real) type class design pattern offers. This is the version of type class pattern as demonstrated in the video Tutorial: Typeclasses in Scala with Dan Rosen. You should really watch it.

Let’s have a parameterized type trait Value[T] that’s supposed to “bridge” the type hierarchies - Expression and Valueable:

trait Value[T] {
  def value(t: T): Valueable
}

The fictitious Calculator library has object Calculator with a single def calculate(v: Valueable): Int method:

object Calculator {
  def calculate(v: Valueable): Int = v.value
}

No Expressions, just Valueables. That’s where the type class pattern shines.

Create object CalculatorEx as follows:

object CalculatorEx {
  def calculate[T : Value](t: T): Int =
    Calculator.calculate(implicitly[Value[T]].value(t))
}

It says that for any type T there’s an implicit conversion to a Value[_] type hierarchy using implicits (that are used in the method via implicitly).

All in all, you need to throw in three more implicits for Number, Plus and Minus so they can be seen as Valueable and participate in def calculate(v: Valueable): Int-based library:

implicit val number2Value = new Value[Number] {
  def value(n: Number): Valueable = new Valueable {
    override def value: Int = n.value
  }
}

implicit val plus2Value = new Value[Plus] {
  def value(p: Plus): Valueable = new Valueable {
    override def value: Int = p.lhs.value + p.rhs.value
  }
}

implicit val minus2Value = new Value[Minus] {
  def value(m: Minus): Valueable = new Valueable {
    override def value: Int = m.lhs.value - m.rhs.value
  }
}

These make it possible to calculate the value of the expression leveraging the fictitious Calculator library:

println(CalculatorEx.calculate(expr))  // prints 20

That’s it! You’re done. If you’ve followed along closely and have developed the “framework” on your own, you should have a complete understanding of the type class design pattern in Scala. Without the type class pattern, blending the Expression type hierarchy with Valueable would not have been possible! And that was the goal of the exercise.

Follow up - All Valueable

Think about using other types, say Int, with the fictitious Calculator library so the following is possible:

println(CalculatorEx.calculate(1))  // prints 1

As the Scala compiler says:

could not find implicit value for evidence parameter of type Value[Int]

All, we need to do to blend Ints as Valueables is to have an implicit that does the conversion.

implicit val int2Value = new Value[Int] {
  override def value(t: Int) = new Valueable {
    override def value: Int = t
  }
}

And that’s it!

As a final exercise would be to reuse implicits and create more complex ones to support “sum” types, like Tuple. I’m leaving it as a homework. Have fun!

Let me know how the homework and the whole blog post went out in the Comments section below. I’d appreciate any comments to improve upon.

References

There are plenty of very good sources on the topic of type classes in general and in Scala, in particular, but the following have done wonders for me:

Comments