Path-dependent types in Scala

November 17, 2016

Last time, I have shown call site type polymorphism as a use case of type parameters. As an extension, I will discuss how the property of type members being path-dependent can be leveraged in practice.

As before, we use type parameters to enforce valid uses on the call site. However, now we go a step further and look at them from different angles as to enhance the expressiveness of Scala code.

Definition

In Scala, a path-dependent type is a type member T that is defined in a base trait B and is kept uninitialised (regardless of optional type constraints). In a child class C, T is instantiated with a concrete type:

trait B { type T }
class C extends B { override type T = Int }

(c: C).T is not a path-dependent type, but if you view the base trait instead, (c: B).T would be path-dependent. In other words, path dependence means that a type T of two instances of the same class C would be two distinct types. In the following example c1.T and c2.T would not be path-dependent:

val c1 = new C
val c2 = new C
implicitly[c1.T =:= c2.T]  // Type equality holds

However, if we downcast to the base trait, we lose information about the type initialisation, which makes T path-dependent:

val b1: B = new C
val b2: B = new C
implicitly[b1.T =:= b2.T]  // Cannot prove that b1.T =:= b2.T

Ownership

Expressing ownership on the type level allows us to ensure correct usage of initialised objects in parent-child relationships. Consider a client which can establish and close its connections:

trait Client {
  type Connection

  def connect: Connection
  def disconnect(connection: Connection): Unit
}

class ClientOps extends Client {
  override type Connection = Int

  override def connect: Connection = 42
  override def disconnect(connection: Connection): Unit = {}
}

object Client {
  def apply(): Client = new ClientOps
}

First, we create a trait with a type member Connection. It will be returned by connect and can be passed to disconnect. Next, we implement this trait, overriding all of its members. Finally, we provide a companion object, instantiating the implementation, but returning the base trait. Now, you can use it as follows:

val client  = Client()
val client2 = Client()

val connection = client.connect

client.disconnect(connection)
client2.disconnect(connection)  // Type mismatch

As you can see, this pattern enables us restrict the usage of a child to its parent class that instantiated it. As connection has the type client.Connection, it cannot be passed as an argument to client2.disconnect which requires client2.Connection.

On the other hand, if you were to use ClientOps directly instead of the apply() method of our companion object, Connection would be instantiated and the second disconnect() becomes valid. Therefore, it is advisable to use access modifiers such as private.

Type mapping

The second pattern are type mappings T => T.M where M is a type member. We consider a function that responds to requests, i.e. we map a request to a response:

sealed trait Request { type R <: Response }
sealed trait Response

object Response {
  case class LogIn(hash: Option[String])
    extends Response
  case class List(users: Seq[String], pages: Int)
    extends Response
}

object Request {
  case class LogIn(username: String, password: String)
    extends Request { override type R = Response.LogIn }
  case class List(page: Int)
    extends Request { override type R = Response.List  }
}

sealed trait Service[R <: Request] {
  def apply(req: R): Future[req.R]
}

implicit object LogInSvc extends Service[Request.LogIn] {
  override def apply(req: Request.LogIn): Future[req.R] =
    Future.successful(Response.LogIn(None))
}

implicit object ListSvc extends Service[Request.List] {
  override def apply(req: Request.List): Future[req.R] =
    Future.successful(Response.List(List.empty, 1))
}

def request[R <: Request](req: R)(implicit svc: Service[R]) =
  svc.apply(req)

By defining a type member for every request, we can implement the Service type class and bind a response type to every request.

This allows us to call request() with a concrete request object and it will return the corresponding response type Future[Response.LogIn]:

val response = request(Request.LogIn("user", "pass"))

To make this pattern more convenient to use, we use a special notation to access child members (#) which allows us to make the response type in Service a type parameter. This enables us to define a companion object to instantiate services. As a consequence, defining new services becomes much easier:

trait Service[Req <: Request, Resp <: Req#R] {
  def apply(req: Req): Future[Resp]
}

object Service {
  def apply[
    Req <: Request, Resp <: Req#R
  ](f: Req => Future[Resp]): Service[Req, Resp] =
    new Service[Req, Resp] {
      override def apply(req: Req): Future[Resp] = f(req)
    }
}

implicit val logInSvc = Service { req: Request.LogIn =>
  Future.successful(Response.LogIn(None))
}

implicit val listSvc = Service { req: Request.List =>
  Future.successful(Response.List(List.empty, 1))
}

Conclusion

In a nutshell, use the ownership pattern when you create a path-dependent value in a parent trait and want to confine all subsequent operations to the parent object. On the other hand, type mappings are especially useful when you want to map a type onto another.

Path-dependent are an underrated feature of the Scala language. I hope this and the previous article could motivate them with real-world examples.

Generated with MetaDocs v0.1.2-SNAPSHOT