Retroactive Polymorphism with Scala Typeclasses :: Jan 31, 2017

As an object-functional language, Scala supports many ways of writing generic, polymorphic code. This article will introduce retroactive polymorphism, and examine the advanced language features enabling it in Scala.

Suppose we are writing a function `sum` that combines the elements of a sequence. The definition is simple with a numeric type like `scala.Int` or `java.lang.Integer`.

Scala


def sum(xs: Seq[Int]): Int = xs.reduce(_ + _)

val ints = Seq(1,2,3)
sum(ints) // 6

Java


public Integer sum(List xs){
    return xs.stream().reduce((x,y) -> x + y).get();
}

List ints = new ArrayList<>();
ints.add(1);
ints.add(2);
ints.add(3);

sum(ints); // 6

When `sum` is generic, however, the elements' capability to combine must be explicitly stated. One approach is declaring an interface `Semigroup[A]`,


trait Semigroup[A]{
  def combine(y: A): A
}

def sum[A <: Semigroup[A]](xs: Seq[A]): A = 
  xs.reduce((x, y) => x.combine(y))

Or in Java:


public interface Semigroup {
    A combine(A y);
}
public > A sum(List xs){
  return xs.stream().reduce(Semigroup::combine).get();
}

Types implementing `Semigroup` can now be passed to `sum`


case class Point(x: Int, y: Int) extends Semigroup[Point]{
  def combine(p: Point): Point = Point(x + p.x, y + p.y)
}

sum(Point(1,2) :: Point(2,5) :: Nil) // Point(3,7)

But it's impossible to retroactivly declare types we don't control (Like `scala.Int`) as `Semigroup`s. Scala offers two workarounds: the Adapter Pattern and Type Classes.

Lets first consider Adapters. Popularized by the Gang of Four and used in Java, we define generic wrappers for every type needed:


trait SemigroupLike[A]{
  def get: A
  def combine(a: SemigroupLike[A]): SemigroupLike[A]
}

case class Point(x: Int, y: Int)

case class SemigroupLikePoint(p: Point) extends SemigroupLike[Point]{
  def get: Point = p
  
  def combine(a: SemigroupLike[Point]): SemigroupLike[Point] =
    SemigroupLikePoint(Point(p.x + a.get.x, p.y + a.get.y))
}

case class SemigroupLikeInt(i: Int) extends SemigroupLike[Int]{
  def get: Int = i
  
  def combine(a: SemigroupLike[Int]): SemigroupLike[Int] =
    SemigroupLikeInt(i + a.get)
}

def sum[A](xs: Seq[SemigroupLike[A]]): A =
  xs.reduce((a,b) => a.combine(b)).get

But this requires users to laboriously create wrapper objects, which is both wordy and unperformant:


val a = SemigroupLikePoint(Point(1,2))
val b = SemigroupLikePoint(Point(2,3))

sum(a :: b :: Nil) // Point(3,5)

val x = SemigroupLikeInt(1)
val y = SemigroupLikeInt(2)

sum(x :: y :: Nil) // 3

Typeclasses circumvent the Adapter Pattern's issues, at the potential cost of greater complexity. Instead of extending type `T` with an interface to declare some behavior `B`, a typeclass implementation is an external object able to perform `B` on `T`. Beginning with the simplest of typeclasses, this post and its follow-ups should progress to the advanced definitions seen in the wild.

As implementations of the typeclass `Semigroup[A]` will be themselves combining elements of type `A`, a second parameter `b` is added to `Semigroup.combine`:


trait Semigroup[A]{
  def combine(a: A, b: A): A
}

case class Point(x: Int, y: Int)

`sum` can now be redefined as:


def sum[A](xs: Seq[A], semi: Semigroup[A]): A =
  xs.reduce(semi.combine)

And used after implementing `Semigroup` for `Point` and `Int`


val pointSemigroup = new Semigroup[Point] {
  def combine(a: Point, b: Point): Point =
    Point(a.x + b.x, a.y + b.y)
}

// As trait `Semigroup` has a single abstract method (SAM),
// Defining implementations with lambda syntax is supported in
// Scala 2.12.X
val intSemigroup: Semigroup[Int] = (a,b) => a + b

val a = Point(1,2)
val b = Point(2,3)
sum(Seq(a,b), pointSemigroup) // Point(3,5)

val x = 1
val y = 2
val z = 3
sum(Seq(x,y), intSemigroup) // 6

intSemigroup.combine(x,y) // 3

There are still many issues with our typeclass, namely:

  • Semigroup instances must be manually passed around
  • It would be preferable in many cases to use infix notation `1.combine(2)` vs `intSemigroup.combine(1,2)`

Implicit parameters solve the former. If a second `implicit` parameter list is added to `sum`, the compiler will attempt to find an implicitly declared instance, first using static scoping rules, and finally by checking the typeclass's static fields. Redeclaring `sum` and `intSemigroup`,


def sum[A](xs: Seq[A])(implicit semi: Semigroup[A]): A =
  xs.reduce(semi.combine)

Or alternatively using [Context Bound](http://docs.scala-lang.org/tutorials/FAQ/context-bounds) syntax,


def sum[A: Semigroup](xs: Seq[A]): A =
  xs.reduce(implicitly[Semigroup[A]].combine)

`sum` can now be called without passing `intSemigroup`


implicit val intSemigroup: Semigroup[Int] =
  (a,b) => a + b

sum(1 :: 2 :: 3 :: Nil) // 6

Implicits also permit a form of ad-hoc polymorphism when used with typeclasses; should a library designer declare common instances in the typeclass's companion object, users are free to pass or implicitly declare alternate definitions.


implicit val reversedStringSemi: Semigroup[String] =
  (a,b) => b + a

trait Semigroup[A]{
  def combine(a: A, b: A): A
}
object Semigroup {
  
  implicit val stringSemigroup: Semigroup[String] =
    (a,b) => a + b
}

// reversedStringSemi found first by compiler
sum("nick" :: "loves" :: "honey" :: Nil) // "honeylovesnick"

To scrap some boilerplate, we define static `Semigroup.apply[A]` to return the implicitly required `Semigroup[A]`.


object Semigroup { 
  def apply[A](implicit ev: Semigroup[A]): Semigroup[A] = ev
  
  ???
}

// or, using context-bound syntax

object Semigroup {
  def apply[A: Semigroup]: Semigroup[A] = implicitly
  
  ???
}

def sum[T: Semigroup](xs: Seq[T]): T =
  xs.reduce(Semigroup[T].combine)

Although I find the context-bound `Semigroup.apply` more appealing, the first version should be used because it can be inlined if desired.

Next up is infix syntax. Scala has [implicit classes](http://docs.scala-lang.org/overviews/core/implicit-classes.html) which allow just that:


object Semigroup {

  ???

  implicit class SemigroupOps[A: Semigroup](lhs: A){

    def combine(rhs: A): A = Semigroup[A].combine(lhs,rhs)

    /** alias for `combine` */
    def |+| (rhs: A): A = Semigroup[A].combine(lhs, rhs)
  }
}

import Semigroup._

Semigroup[String].combine("foo", "bar") // "foobar"
"foo" |+| "bar" // "foobar"

Regular implicit classes create a lot of wrapper objects, so `SemigroupOps` should be restructured as a [Value Class](http://docs.scala-lang.org/overviews/core/value-classes.html), which doesn't allocate any runtime objects when used correctly.


implicit class SemigroupOps[A](val lhs: A) extends AnyVal{

  def combine(rhs: A)(implicit semi: Semigroup[A]): A =
    semi.combine(lhs, rhs)

  /** alias for `combine` */
  def |+| (rhs: A)(implicit semi: Semigroup[A]): A =
    semi.combine(lhs, rhs)
}

Conclusions

Typeclasses are a powerful means of achieving retroactive polymorphism. In future posts, I hope to cover the different styles used by open source libraries like [spire](https://github.com/non/spire) and [cats](typelevel.org/cats/), with usability and performance considerations.

The final code can be found here.

Notes

It should also be mentioned that while Structural Types can be used in similar ways, the feature relies on runtime reflection and is discouraged from use.