title: Chaining implicits via the shortest route
body: <h2>Problem</h2>
  
  <p>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.</p>
  
  <p>I had prepared simple example that shows my futile attempts to declare such implicits.</p>
  
  <pre><code>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
  }
  </code></pre>
  
  <p>I introducing following test case conversions: <em>A -> B, A -> BB, B -> C, B -> D, C -> D</em>.</p>
  
  <p>I tried two approaches and they give me different implicit resolution errors.</p>
  
  <h2>Transit chaining</h2>
  
  <pre><code>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)
  }
  </code></pre>
  
  <p>Such approach made possible path resolution between <em>A -> B -> C -> D</em> and <em>A -> B -> D</em>, compiler choose the latter route. But it fails if there is any branching</p>
  
  <h2>Continuation passing</h2>
  
  <pre><code>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)
  }
  </code></pre>
  
  <p>In that case the compiler could ignore non-relevant <em>A -> BB</em> conversion. But it fails to resolve conflict <em>A -> B -> C -> D</em> and <em>A -> B -> D</em></p>
  
  <h2>What I'm searching for</h2>
  
  <p>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 <em>weight</em> to make <em>A -> B -> D</em> and <em>A -> C -> D</em> distinguishable. There is some black magic behind implicit resolution priority and I hope it could help.</p>
  
  <p>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.</p>