I think we can easily keep the subtype encoding of type classes and resolve ambiguity errors at the same time by just narrowing the type signatures of implicit instances.
Let’s ask – what prevents us from choosing an arbitrary instance in case of ambiguity?
It’s only the fact that when we get two opaque implicit values in our implicit search: Monad[F] and Traversable[F], we can’t possibly know if the underlying Functor[F] is the same for both.
If we knew, we could pick either of them. But we could just directly check if they’re the same!
Let’s start with the usual suspects:
trait Functor[F[_]] { def map[A, B](f: A => B): F[B] }
trait Monad[F[_]] extends Functor[F]
trait Traversable[F[_]] extends Functor[F]
trait Maybe[A]
object Maybe {
trait FunctorImpl extends Functor[Maybe] {
final def map[A, B](f: A => B): Maybe[B] = ???
}
implicit val maybeMonad: Monad[Maybe] = new Monad[Maybe] with FunctorImpl { ??? }
implicit val maybeTraversable: Traversable[Maybe] = new Traversable[Maybe] with FunctorImpl { ??? }
}
When we try to summon an implicit value, we’ll get an ambiguity error.
implicitly[Functor[Maybe]] // error
We know that both maybeMonad and maybeTraversable are inheriting the implementation of Functor[Maybe] from FunctorImpl, we also know that map in FunctorImpl is final, so neither of them could override it.
We have ample evidence that both of these implementations are equivalent with respect to Functor, but unfortunately, we hid it from the compiler by widening the type back to Monad[Maybe] and removing the mention of FunctorImpl, let’s fix that mistake:
implicit val maybeMonad: Monad[Maybe] with FunctorImpl = new Monad[Maybe] with FunctorImpl { ??? }
implicit val maybeTraversable: Traversable[Maybe] with FunctorImpl = new Traversable[Maybe] with FunctorImpl { ??? }
Or just omit the signatures and let the compiler infer the narowest type:
implicit final val maybeMonad = ???
implicit final val maybeTraversable = ???
Now the compiler, too, has direct unfalsifiable evidence that both of the implementations are the same, it only needs to glance at the type signature to verify it. At this point it can safely pick either instance, knowing that they both point to the same trait.
implicitly[Functor[Maybe]] // good, all the instances are just FunctorImpl in disguise
In more detail, when encountering an ambiguity over some type T, for each ambiguous instance,
the resolver should try to find the latest base class that implements T with all T methods as final, if all found base classes are the same for every instance, the compiler now has direct evidence that all implementations of Tin the search are the same and can pick any of them.
Alternatively, a more exhaustive scheme would be to extract the set of methods of T and verify that for each ambiguous instance, there is a final implementation of each method with the same ‘source’. This would allow two methods of T to be finaly implemented by two different traits, but still correctly disambiguated.
For library authors, the scheme would entail two minor changes to their workflow:
- they would have to specify the narrowest type for their implicit values, instead of widening them
- they would have to
final their methods
For users of implicit there would be no changes at all – they would just suddenly stop getting ambiguity errors! They wouldn’t have to specify coherence domains in their implicit summons and they wouldn’t lose the ability to declare orphans and local instances.
This scheme does not substitute for coherence in all cases, but it solves the problem of ambiguity in a straightforward and obvious manner without imposing any draconian restrictions on the users.
Implementation: the scheme is a simple enough extension as to be implementable today as an implicit macro or as a compiler plugin.
Caveats: If an implicit value is taken and re-assigned to a variable with a widened type, it’s disambiguation properties are lost. However, coherent domains exhibit the same properties if an implicit in a domain is re-assigned to a domainless value.
A variant of this scheme can also be implemented if Scala gets first-class delegation, e.g:
final val functorMaybe: Functor[Maybe] = ???
implicit val maybeMonad: Monad[Maybe] with (Functor[Maybe] by functorMaybe.type)
implicit val maybeTraversable: Traversable[Maybe] with (Functor[Maybe] by functorMaybe.type)
Would be resolved because the singleton types which implement the Functor class are proven the same.
