aaronlevin aaronlevin - 10 months ago 40
Scala Question

Scalac cannot infer inductively built path-dependent type

I'm working on a port of

to Scala. The idea is to use typeclass resolution to inductively build functions that can handle requests. I'm running into some weird inference issues I can't quite figure out.

object Servant {

class :>[Path, A]

trait HasServer[A] {
type ServerT

def route(a: ServerT): String

implicit val unitServer = new HasServer[Unit] {
type ServerT = String

def route(str: ServerT): String = str

implicit def subServer[A, Sub](implicit sub: HasServer[Sub]) = new HasServer[A :> Sub] {
type ServerT = A => sub.ServerT

def route(handler: ServerT): String = "handler"


With the above, the following fails to compile:

val foo = implicitly[HasServer[Int :> Unit]]
implicitly[=:=[Int => String, foo.ServerT]]

The error is:

servant.scala:33: error:
Cannot prove that Int => String =:= Main.$anon.Servant.foo.ServerT.

However, it will compile if I instantiate
HasServer[Int :> Unit]
directly, via:

val foo = new HasServer[Int :> Unit] {
type ServerT = Int => unitServer.ServerT

def route(handler: ServerT): String = handler(10)

How can I get this to compile? Thanks!

Answer Source

The problem is all in the definition of implicitly ...

def implicitly[T](implicit e: T) = e

implicitly[T] will only ever give you a value which is typed as T, never anything more precise. In the case above, that's HasServer[Int :> Unit] which, crucially, leaves the member type ServerT unconstrained.

This is commonly worked around by defining a per type class companion object apply method which preserves the desired refinement, eg.,

object HasServer {
  def apply[T](implicit hs: HasServer[T]):
    HasServer[T] { type ServerT = hs.ServerT } = hs

the result type here is a little unwieldy, so it's also common to combine this with the "Aux" pattern,

object HasServer {
  type Aux[T, S] = HasServer[T] { type ServerT = S }
  def apply[T](implicit hs: HasServer[T]): Aux[T, hs.ServerT] = hs

which will probably come in handy elsewhere in any case.

We can see the difference this makes to the inferred types on the REPL,

scala> implicitly[HasServer[Int :> Unit]]
res0: Servant.HasServer[Servant.:>[Int,Unit]] = ...

scala> HasServer[Int :> Unit]
res1: Servant.HasServer[Servant.:>[Int,Unit]]{type ServerT = Int => String} = ...

This refinement will be inferred as the type of a val definition, so now you'll get the desired result,

scala> val foo = HasServer[Int :> Unit]
foo: Servant.HasServer[Servant.:>[Int,Unit]]{type ServerT = Int => String} = ...

scala> implicitly[=:=[Int => String, foo.ServerT]]
res2: =:=[Int => String,foo.ServerT] = <function1>

There are a number of ways that the definition of implicitly could be improved to avoid this problem. The following is the most straightforward for reference types,

def implicitly[T <: AnyRef](implicit t: T): t.type = t

and if literal types are enabled we could removed the <: AnyRef bound and define it for all types,

def implicitly[T](implicit t: T): t.type = t

shapeless provides a the[T] operator which behaves similarly to the latter via a macro.