Scala self-recursive types

One of the advantages of using a statically typed language is that you can use the type system to enforce some constraints. Scala provides self-recursive types, aka F-bounded polymorphic types that–along with self types–let you put powerful constraint to your type definitions.

Self-recursive type definition

Terminology apart, let me show you one of the use cases where this could be useful. Consider the following example which does not use a self-recursive type:

trait Doubler[T] {
  def double: T
}

case class Square(base: Double) extends Doubler[Square] {
  override def double: Square = Square(base * 2)
}

So far so good, the compiler will not complain. The problem is that it won’t complain even if you write something outrageous like the following code:

case class Person(firstname: String, lastname: String, age: Int)

case class Square(base: Double) extends Doubler[Person] {
  override def double: Person = Person("John", "Smith", 42)
}

You want to avoid something like that by enforcing a compile-time check. Enters a self-recursive type:

trait Doubler[T <: Doubler[T]] {
  def double: T
}   

By using this definition of Doubler you’re saying: “Hey, if someone tries to extends Doubler with a type which doesn’t extend Doubler in turn (hence self-recursive), do not compile it”. In this case the previous definition of Square, which extends Doubler[Person], doesn’t compile.

Note that self-recursive types are not specific to Scala. Indeed Java uses them too. Take, for example, the Enum definition:

public abstract class Enum<E extends Enum<E>> implements Comparable<E>, Serializable {
...
}

E extends Enum<E> in Javanese means exactly E <: Enum[E]

Self type definition

F-bounded polymorphic types are of great help but sometimes they are not enough to enforce the constraints you need. Indeed, the previous definition of Doubler has still one problem. Consider the next code:

trait Doubler[T <: Doubler[T]] {
  def double: T
}

case class Square(base: Double) extends Doubler[Square] {
  override def double: Square = Square(base * 2)
}

case class Apple(kind: String) extends Doubler[Square] {
  override def double: Square = Square(5)
}

Can you spot the problem? Look at the Apple definition, it extends Doubler[Square] instead of Doubler[Apple].

This code compiles because it respects the constraint put by the Doubler definition. Indeed Square extends Doubler so it can be used in Apple. Sometimes this is what you want in which case the self-recursive type will do. In cases when you don’t want this to happen a self type can work this out:

trait Doubler[T <: Doubler[T]] { self: T =>
  def double: T
}

Now if you try to compile the previous definition of Apple the compiler will complain by saying something like:

error: illegal inheritance;
 self-type Apple does not conform to Doubler[Square]'s selftype Square
       case class Apple(kind: String) extends Doubler[Square] {
                                              ^

Conclusions

If you’re thinking: “Come on! I would never extend Apple that way because I know what I meant when I wrote my Doubler abstraction. I don’t need then the self type annotation and, since I know what I’m doing, I don’t need the self-recursive type either”. Well you may be right but I’d have two objections:

1. Generally you are not the only one working on a project and, anyway, a good rule of thumb is to design your software as if you’re designing a public API. In this case you want to be sure no one will use your API in the wrong way.

2. Compilers are implemented by smart guys, generally. Having the compiler help by your side is always a good thing in my humble opinion.

Are there alternatives to this type of problems? Yes indeed, Type Classes, which is by the way the option I prefer. But this is another story for a future post.