developer blog

Back to Originate.com

Recursive Type Signatures in Scala

Have you seen a type signature like this before?

1
trait T[U <: T[U]]

If you’re like me, you’ve come across this type signature, and you’re wondering what the heck it means. You likely Googled something like “recursive type” or “self-referential type” and ended up here.

So what does this type signature mean? Why not use trait T[U]?

To understand the meaning of T[U <: T[U]], we’ll work through a simple example.

Example

Suppose we want database entities with CRUD methods. We could define them like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// I don't know about you, but I like to name my fruit.
case class Apple(name: String, price: Double) {
  def create(entityData: String): Apple
  def read(id: String): Option[Apple]
  def update(f: Apple => Apple): Apple
  def delete(id: String): Unit
}

case class Bird(name: String, birthday: DateTime) {
  def create(entityData: String): Bird
  def read(id: String): Option[Bird]
  def update(f: Bird => Bird): Bird
  def delete(id: String): Unit
}

But we can see that these classes look nearly identical. In addition, any new CRUD entities we add will expose the same CRUD methods. Now, should we abstract the interface into a trait? Let’s see what happens when we do:

1
2
3
4
5
6
7
8
9
10
trait CrudEntity {
  def create(entityData: String): CrudEntity
  def read(id: String): Option[CrudEntity]
  def update(f: CrudEntity => CrudEntity): CrudEntity
  def delete(id: String): Unit
}

case class Apple(name: String, age: Int) extends CrudEntity

case class Bird(name: String, hobby: String) extends CrudEntity

Well this sucks. Our method signatures don’t fully express what we want. We’ve lost the ability to ensure that e.g. calling update on an Apple returns an Apple. As is, it can return any CrudEntity. Let’s try to regain some specificity by adding a type parameter to our CrudEntity trait:

1
2
3
4
5
6
7
8
9
10
trait CrudEntity_2[E] {
  def create(entityData: String): E
  def read(id: String): Option[E]
  def update(f: E => E): E
  def delete(id: String): Unit
}

case class Apple(name: String, age: Int) extends CrudEntity_2[Apple]

case class Bird(name: String, hobby: String) extends CrudEntity_2[Bird]

Okay, better. But we still haven’t locked this down. Our types don’t yet express exactly what we want. Do you see the problem?

The problem is that someone can extend CrudEntity_2 in a way we didn’t intend them to:

1
case class Orange(name: String, bankAccount: Double) extends CrudEntity_2[FloobyDust]

Whoa! In the code above, CrudEntity_2[E] does not restrict the type of E, so they can use anything they want, without complaint from the compiler — FloobyDust, Potato, BurritoAstronaut, you name it.

This is no bueno. Instead, we’d like them to get a big, fat compiler error if they try extending anything other than CrudEntity_2[Orange]. How do we ensure that E matches the class we’re defining?

Let’s try defining CrudEntity again. This time, we’ll use type bounds:

1
2
3
4
5
6
7
8
9
10
trait CrudEntity_3[E <: CrudEntity_3[E]] {
  def create(entityData: String): E
  def read(id: String): Option[E]
  def update(f: E => E): E
  def delete(id: String): Unit
}

case class Apple(name: String, age: Int) extends CrudEntity_2[Apple]

case class Bird(name: String, hobby: String) extends CrudEntity_2[Bird]

Better. Now we’ve constrained E to be a subtype of CrudEntity. No more FloobyDust. But there’s one last problem, and you can probably guess what it is. We haven’t yet ensured that E matches our class type, only that it subclasses CrudEntity. CrudEntity is still open for abuse:

1
case class Orange(name: String, age: Int) extends CrudEntity_3[Apple]

Yuck! To take care of this, we need a way to ensure that e.g. Orange extends CrudEntity_3[Orange]. For this assurance, we’ll use a self type.

Here is our final definition of CrudEntity, which uses a self type:

1
2
3
4
5
6
trait CrudEntity[E <: CrudEntity[E]] { self: E =>
  def create(entityData: String): E
  def read(id: String): Option[E]
  def update(f: E => E): E
  def delete(id: String): Unit
}

self: E => ensures that any concrete class that extends CrudEntity must be of type E and that code like

1
case class Orange(name: String, age: Int) extends CrudEntity[Apple]

will get rejected by the compiler because Orange is not of type Apple.

Now we can rest, confident that our definition of CrudEntity ensures that any subtype of CrudEntity[E] must in fact be an E. This definition gives us the semantics we desire, and enlists the compiler to reject all code in violation.

Comments