Chaining implicits via the shortest route

Question

Problem

I have a set of types and set of conversions between them. That sounds like DAG and have some similarities to it. I'd like to be able to compute implicitly shortest conversion path between any two types if it is feasible.

I had prepared simple example that shows my futile attempts to declare such implicits.

final case class A(u : Int)
final case class B(u : Int)
final case class BB(u : Int)
final case class C(u : Int)
final case class D(u: Int)

trait Convert[F,T] {
  def convert(source : F) : T
}

I introducing following test case conversions: A -> B, A -> BB, B -> C, B -> D, C -> D.

I tried two approaches and they give me different implicit resolution errors.

Transit chaining

trait ConcreteConvert[F,T] extends Convert[F,T]

class Transit[F,M,T](implicit fm : ConcreteConvert[F,M], mt : Convert[M,T]) extends Convert[F,T] {
  override def convert(source : F) : T =
    mt.convert( fm.convert(source) )
}

object Implicits {
  implicit def transit[F,M,T](implicit fm : ConcreteConvert[F,M], mt : Convert[M,T]) : Convert[F,T] =
    new Transit()(fm, mt)

  implicit object A2B extends ConcreteConvert[A,B] {
    override def convert(source : A) : B = B(source.u)
  }
  implicit object B2C extends ConcreteConvert[B,C] {
    override def convert(source : B) : C = C(source.u)
  }
  /*implicit object A2BB extends ConcreteConvert[A,BB] {
    override def convert(source : A) : BB = BB(source.u)
   }*/ // compilation fails
  implicit object C2D extends ConcreteConvert[C,D] {
    override def convert(source : C) : D = D(source.u)
  }
  implicit object B2D extends ConcreteConvert[B,D] {
    override def convert(source : B) : D = D(source.u)
  }
}

object Usage {
  import Implicits._
  def conv[F,T](source : F)(implicit ev : Convert[F,T]) : T =
    ev.convert(source)

  val a = A(0)
  val b = conv[A,B](a)
  val c = conv[A,C](a)
  val d = conv[A,D](a)
}

Such approach made possible path resolution between A -> B -> C -> D and A -> B -> D, compiler choose the latter route. But it fails if there is any branching

Continuation passing

abstract class PostConvert[F, M, T](mt : Convert[M,T]) extends Convert[F,T] {
  def pre(source : F) : M

  override def convert(source : F) : T =
    mt.convert( pre(source) )
}

class IdConvert[F]() extends Convert[F,F] {
  override def convert(source : F) : F =
    source
}

object ImplicitsPost {
  implicit def idConvert[F] : Convert[F,F] =
    new IdConvert[F]()

  implicit def a2b[T](implicit mt : Convert[B,T]) = new PostConvert[A,B,T](mt) {
    override def pre(source : A) : B = B(source.u)
  }
  implicit def a2bb[T](implicit mt : Convert[BB,T]) = new PostConvert[A,BB,T](mt) {
    override def pre(source : A) : BB = BB(source.u)
  }
  implicit def b2c[T](implicit mt : Convert[C,T]) = new PostConvert[B,C,T](mt) {
    override def pre(source : B) : C = C(source.u)
  }
  implicit def c2d[T](implicit mt : Convert[D,T]) = new PostConvert[C,D,T](mt) {
    override def pre(source : C) : D = D(source.u)
  }
  /*implicit def b2d[T](implicit mt : Convert[D,T]) = new PostConvert[B,D,T](mt) {
    override def pre(source : B) : D  = D(source.u)
  }*/ // compiler fails
}

object UsagePost {
  import ImplicitsPost._
  def conv[F,T](source : F)(implicit ev : Convert[F,T]) : T =
    ev.convert(source)

  val a = A(0)
  val b = conv[A,B](a)
  val c = conv[A,C](a)
  val d = conv[A,D](a)
}

In that case the compiler could ignore non-relevant A -> BB conversion. But it fails to resolve conflict A -> B -> C -> D and A -> B -> D

What I'm searching for

Some way to solve problem in generic way. I could define relation graph and let implicit mechanics to choose the shortest way in it. It would be better if I could adjust each conversion weight to make A -> B -> D and A -> C -> D distinguishable. There is some black magic behind implicit resolution priority and I hope it could help.

Implicits is said to be very computation powerful instrument, several minutes of compiler work worth in intricate cases. So I keep hope that arbitrary long transitive conversions are possible with some tricky technique.

Answer 1

Short answer

You can't solve this problem in it's current wording using scala implicit resolution, because it does not support backtracking.

Practical answer

You best bet would probably be to modify the scala compiler to support backtracking in implicit resolution, which should be enough for your first implementation to work.

Long answer

I lied, it should be possible with the current state of the compiler, but it's won't be as nice as the equivalent Prolog program you would write, and probably be out of the scope of "oh this should be fun to write at the type level" ;). Let me first rephrase your problem.

Given a few types:

trait A; trait B; trait B; trait C; trait D

And a directed graph on these types:

trait Edge[X, Y]

def fact[X, Y] = new Edge[X, Y] {}

implicit val edge0: Edge[A, B]  = fact //   ( A )
implicit val edge1: Edge[A, BB] = fact //   ↓   ↓
implicit val edge2: Edge[B, C]  = fact // ( B ) BB
implicit val edge3: Edge[B, D]  = fact // ↓   ↓
implicit val edge4: Edge[C, D]  = fact // C → D

Find the shortest path between A and D using implicit resolution.

To see what's tricky in this problem, it's useful to decompose it into two parts:

1. Lift these implicit edges into a type level representation of the graph starting from node A, something like:

   A 
     :: (B
       :: (C :: (D :: HNil) :: HNil)
       :: (D :: HNil)
       :: HNil)
     :: (BB :: HNil)
     :: HNil
   

2. Do a type level BFS on this representation.

Surprisingly, 1. is trickier that it sounds, and that's because scala implicit resolution does not do backtracking. You would have to adopt a slightly different representation of the graph for this to be possible.

One solution, which sticks to your original formulation (one implicit per edge), could be to use a technique similar to the exposed in this example, which uses two trait EdgeLeft[X, Y] & trait EdgeRight[X, Y] instead of a trait Edge[X, Y], and gather all the edges of the graph into a single HList effectuvely working around the lack of backtracking.

You could also make your life much simpler by encoding you graph in a representation closer to an adjacency matrix, such as with a implicit fact: Neighbours[A, B :: BB :: HNil]. But either way, a slight change on your graph representation should be enought to let you construct a structure equivalant to the above representation of you graph.

Solving 2. won't be easy, but it should theoretically not be harder that writing pure, value level DFS on the following input, and lifting it to the type level:

val input: List[Any] = (
  "A" 
    :: ("B"
      :: ("C" :: ("D" :: Nil) :: Nil)
      :: ("D" :: Nil)
      :: Nil)
    :: ("BB" :: Nil)
    :: Nil
)

def DFS(i: List[Any]): List[String] = ???

Answer 2

I don't think it's possible to solve this problem with the tools currently available in Scala.

Let's step back and ask how would we solve this problem in general? If you think about this problem for a moment you'll realize that it is equivalent to solving shortest-path on a graph. In this case the nodes of the graph are the concrete classes (here A, B, BB, C, and D) and the edges are the values in the Convert typeclass.

The standard way to solve shortest-path is Dijkstra's Algorithm, which just reduces to a breadth-first search for unweighted graphs, which is what we have here. So how do we do a breadth-first search through this graph?

Per wikipedia here is the pseudo-code for breadth-first search:

     1 Breadth-First-Search(Graph, root):
     2 
     3     for each node n in Graph:            
     4         n.distance = INFINITY        
     5         n.parent = NIL
     6 
     7     create empty queue Q      
     8 
     9     root.distance = 0
    10     Q.enqueue(root)                      
    11 
    12     while Q is not empty:        
    13     
    14         current = Q.dequeue()
    15     
    16         for each node n that is adjacent to current:
    17             if n.distance == INFINITY:
    18                 n.distance = current.distance + 1
    19                 n.parent = current
    20                 Q.enqueue(n)

There are two places in this algorithm where we need to enumerate all the nodes in the graph that match some predicate. On line 3 we need to enumerate ALL the nodes in the graph. This is in principle possible to do and shapeless offers a path forward on that, assuming the nodes form an ADT, which they easily could.

However, on line 16 we need to enumerate the adjacent nodes to the one we have. To do that we would need to analyze all the edges in our graph, which entails enumerating all the implicits of a certain shape: if A is our node, then we want all typeclass members that match Convert[A,_].

Scala offers no way to enumerate those typeclass members via the mechanism of implicits. The reason is that the mechanism for requesting an implicit allows you to request at most ONE implicit and if any ambiguous (i.e. multiple equally ranked) implicits are discovered then it is considered an error. Consider what would happen if we requested all the edges for node B:

def adjacentToB[OtherNode](implicit edges:Convert[B,OtherNode]) = edges

Because the above call would be satisfied by both Convert[B,C] and Convert[B,D] the compiler would give us an error.

Side note: you may think you could solve this using a more prolog-inspired depth-first search. Unfortunately I think you'll be stymied by the exact same issue.