Retroactive Polymorphism with Scala Typeclasses

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<Integer> xs){
    return xs.stream().reduce((x,y) -> x + y).get();
}

List<Integer> 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> {
    A combine(A y);
}
public <A extends Semigroup<A>> A sum(List<A> 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 Semigroups. 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 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 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, 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 and 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.