Call site type polymorphism

October 12, 2016

Motivation

It is a common problem to define class hierarchies. To prevent duplication, shared functionality should be ideally kept in base traits. Oftentimes, a problem arises that in the base trait we do not know the return type of a child function:

sealed trait Base {
  def change: Base
}
case class Child() extends Base {
  override def change: Base = this
}

Child().change: Base

In other words, for a class F we want to define methods in its base trait. These methods should have the return type F. In this article, I am going to outline different ways how to solve this particular problem in Scala.

Covariance

Consider a simple binary tree:

sealed trait Tree
case class Leaf(value: Int) extends Tree
case class Branch(left: Tree, right: Tree) extends Tree

Branch(Leaf(1), Branch(Leaf(2), Leaf(3)))

We are going to leverage the fact that functions are covariant in their return types. Let us extend our hierarchy by a map() function:

sealed trait Tree {
  /** Recursively apply `f` to all children */
  def map(f: Tree => Tree): Tree
}
case class Leaf(value: Int) extends Tree {
  override def map(f: Tree => Tree): Leaf = this
}
case class Branch(left: Tree, right: Tree) extends Tree {
  override def map(f: Tree => Tree): Branch =
    Branch(f(left).map(f), f(right).map(f))
}

val tree = Branch(Leaf(1), Branch(Leaf(2), Leaf(3)))
tree.map(identity): Branch

In the base trait we defined the function prototype, and overrode this function with the return types of the actual child classes. Thanks to covariance map() returns Leaf or Branch, respectively.

Type parameters

What if our hierarchy is a little more complicated and has several nested branch types with shared functionality? Let us consider a type-safe representation of HTML, where tags like div and b are represented as separate types:

sealed trait Node {
  def map(f: Node => Node): Node
}
case class Text(value: String) extends Node {
  override def map(f: Node => Node): Text = this
}
sealed trait Tag extends Node {
  def children: Seq[Node]
  def withChildren(children: Seq[Node]): Tag
  override def map(f: Node => Node): Tag =
    withChildren(children.map(f(_).map(f)))
}
case class Div(id: Option[String],
               children: Node*) extends Tag {
  override def withChildren(children: Seq[Node]): Div =
    Div(id, children: _*)
}
case class B(children: Node*) extends Tag {
  override def withChildren(children: Seq[Node]): B =
    B(children: _*)
}

val div = Div(None, B(Text("Hello")))
div.map(identity): Tag

We defined a trait Tag that defines functions available on all tag nodes. Hereby, we can keep our tag classes succinct. But as withChildren() is called by map() from within Tag, it comes at the price that we cannot return the concrete type in map(). Thus, map() returns Tag when called on any tag node.

As in our example where we provide tag-specific attributes, this turns out to be a severe limitation. For example, id could not be accessed in this example on the return value of map.

We could attempt to solve it by adding a type parameter to the base trait:

sealed trait Node[T] {
  def map(f: Node[_] => Node[_]): T
}
case class Text(value: String) extends Node[Text] {
  override def map(f: Node[_] => Node[_]): Text = this
}
sealed trait Tag[T <: Tag[_]] extends Node[T] {
  def children: Seq[Node[_]]
  def withChildren(children: Seq[Node[_]]): T
  override def map(f: Node[_] => Node[_]): T =
    withChildren(children.map(f(_).map(f)
      .asInstanceOf[Node[_]]))
}
case class Div(id: Option[String],
               children: Node[_]*) extends Tag[Div] {
  override def withChildren(children: Seq[Node[_]]): Div =
    Div(id, children: _*)
}

val div = Div(None, Text("Hello"))
val mapped: Div = div.map(identity)

While it works as expected, you see that our solution got unwieldy, requiring many wildcards and even type casts.

This approach is also called F-bounded type polymorphism. You can find more information in this article.

Type members

Luckily, Scala provides us with type members a better alternative:

sealed trait Node {
  type T <: Node
  def map(f: Node => Node): T
}
case class Text(value: String) extends Node {
  override type T = Text
  override def map(f: Node => Node): Text = this
}
sealed trait Tag extends Node {
  override type T <: Tag
  def children: Seq[Node]
  def withChildren(children: Seq[Node]): T
  override def map(f: Node => Node): T =
    withChildren(children.map(f(_).map(f)))
}
case class Div(id: Option[String],
               children: Node*) extends Tag {
  override type T = Div
  override def withChildren(children: Seq[Node]): Div =
    Div(id, children: _*)
}

val div = Div(None, Text("Hello"))
div.map(identity): Div

It still works the same, but is a much more elegant solution than type parameters.

One caveat: We cannot override type T in Tag with a concrete type, otherwise the return type of withChildren() and map will be fixed and cannot be changed in child classes. However, we can refine the type constraint on T, which is what we have done in our solution with override type T <: Tag.

Type members also work if our base class is already parameterised. Consider a list type:

trait MySeq[T] {
  type Child[T] <: MySeq[T]
  def map[U](f: T => U): Child[U]
}

class MyList[T] extends MySeq[T] {
  override type Child[T] = MyList[T]
  override def map[U](f: T => U): Child[U] = new MyList[U]
}

class MyVector[T] extends MySeq[T] {
  override type Child[T] = MyVector[T]
  override def map[U](f: T => U): Child[U] = new MyVector[U]
}

Note that if MySeq[T] was covariant (i.e. trait MySeq[+T]), the compiler requires you to indicate this as well in the type member: type Child[+T] <: MySeq[T].

this.type

An even easier solution I only recently learned about would be to use the type this.type:

sealed trait Node {
  def map(f: Node => Node): this.type
}
case class Text(value: String) extends Node {
  override def map(f: Node => Node): this.type = this
}
sealed trait Tag extends Node {
  def children: Seq[Node]
  def withChildren(children: Seq[Node]): this.type
  override def map(f: Node => Node): this.type =
    withChildren(children.map(f(_).map(f)))
}
case class Div(id: Option[String],
               children: Node*) extends Tag {
  override def withChildren(children: Seq[Node]): this.type =
    Div(id, children: _*).asInstanceOf[this.type]
}

val div = Div(None, Text("Hello"))
div.map(identity): Div

There are two downsides to this approach: First, it requires a type cast because the function is expected to return this.

Second, this.type cannot be parameterised. In the following example, we would expect map() on all children C[T] to return C[U] instead of C[T]:

trait MySeq[T] {
  def map[U](f: T => U): this.type
}

class MyList[T] extends MySeq[T] {
  override def map[U](f: T => U): this.type = ???
}

class MyVector[T] extends MySeq[T] {
  override def map[U](f: T => U): this.type = ???
}

Unfortunately, the type parameter is implicitly included in this.type, whereby this.type[U] would result in a syntax error.

Examples

We used the same technique in MetaWeb to provide type-safe bindings for HTML. See this file for our tree implementation.

Conclusion

We have seen a couple of ways to use the call site type in hierarchies. Whenever possible, try to make use of Scala's covariance property. If your ADT is more complicated than that, type parameters or this.type are the preferred solutions.

In a follow-up article, I am going to talk about path-dependent types and motivate them with real-world scenarios.

Generated with MetaDocs v0.1.2-SNAPSHOT