Composing type-level functions with implicit witnesses

Question

I am experimenting with some rather complex type-level calculations. There, I have some type tags (say, A, B, and C), and functions working on them, which are represented by implicit witnesses with path-dependent result types:

class A
class B
class C

trait F1[T] { type result }
trait F2[T] { type result }

implicit object f1OfA extends F1[A] { type result = B }
implicit object f2OfB extends F2[B] { type result = C }

trait Composed[T] { type result }

In the course of calculations, when "implementing" Composed, I need to make use of the fact that I can, given the above code, in principle transform A to C (in this example, I just need the composition, but actually there's more things involved).

However, I don't know how to express the composition, as I am always limited by the restriction that implicits are not transitively applied; the following code fails with "implicit not found":

implicit def composed1[X](implicit f2DotF1OfX: F2[F1[X]]): Composed[X] =  
  new Composed[X] { type result = f2DotF1OfX.result }

implicitly[Composed[C]]

What I actually tried to write initially was the following:

implicit def composed2[X](implicit f1OfX: F1[X], f2OfLast: F2[f1OfX.result]): Composed[X] =
  new Composed[X] { type result = f2OfLast.result }

This of course failed because there I used f1OfLast in the same parameter list it is defined. If it were not an implicit parameter, I could write

implicit def composed3a[X](f1OfX: F1[X])(f2OfLast: F2[f1OfX.result]): Composed[X] =
   new Composed[X] { type result = f2OfLast.result }

But it is not possible to do this using two implicit parameter lists, since they are disallowed by the language.

---

In short: how can I get a witness for F2[F1[X]] in the above examples? If necessary, I could also change the way of writing type-level functions, but I have not yet found another way to express them.

Answer 1

You use another type parameter and then require f1OfX.result to be that:

implicit def composed4[X, Y](implicit f1OfX: F1[X] { type result = Y },
  f2OfLast: F2[Y]): Composed[X] =
    new Composed[X] { type result = f2OfLast.result }