Implicit cannot derive any possible type that you could compose from your rules, because it would easily end up in situation then you have an infinite number of possibilities:
id[X]: X => X
x: A => B
y: B => C
could be composed
z = x andThen y
but maybe it could be generated with
z = x andThen id[B] andThen y // or
z = id[A] andThen x andThen y // or
z = x andThen y andThen id[C] // or
z = id[A] andThen x andThen y andThen id[C] //
...
You see where this is going?
Meanwhile derivation should be unambiguous, when you start with your "primitives" implicits and you try to compose them into your "target" implicit, there should be only one possible way. The moment Scala finds that there is some ambiguity, it stops deriving.
In your example you are composing ConversionRate[X, USD] with ConversionRate[Y, USD] into ConversionRate[X, Y]. But it doesn't prevent you from doing something like:
ConversionRate[USD, USD] combine with
ConversionRate[USD, USD] combine with
ConversionRate[USD, USD] combine with...
One way of doing this would be defining your conversions in such a way that there should be only one way of doing it, that you cannot easily break, e.g.:
case class USDConversionRate[A <: Currency](rate: Double)
// implicit conversion rates
case class ConversionRate[X <: Currency, Y <: Currency](rate: Double) extends AnyVal
object ConversionRate {
implicit def combine[X <: Currency, Y <: Currency](
implicit
ev1: X =:!= USD.type, // available in shapeless
ev2: Y =:!= USD.type, // proves type inequality
ev3: X =:!= Y, // which we use to force only one way to derive each pair
xFromUSD: USDConversionRate[X],
yFromUSD: USDConversionRate[Y],
): ConversionRate[X, Y] = ...
implicit def toUSD[X <: Currency](
implicit X =:!= USD.type,
xFromUSD: USDConversionRate[X]
): ConversionRate[X, USD.type] = ...
implicit def fromUSD[X <: Currency](
implicit X =:!= USD.type,
xFromUSD: USDConversionRate[X]
): ConversionRate[USD.type, X] = ...
implicit def unit: ConversionRate[X, X] = ...
}
Here you would use type bounds to cut all cycles. In original code they would appear if you'd use e.g. inverse (because anything that would derive X -> Y, would conflict with inverse(inverse(X -> Y))), etc, same with traverse and unit, etc. You have to guarantee that expansion cannot diverge and anything that would lead to cycle, or any other 2 different ways to get to the same type are forbidden.
Your biggest problem is that with 2 parameter composition like this: A -> B, you can always try to do it through something else A -> C -> B, A -> D -> B, so the best way is to remove any possibility of going through some extra steps. My proposition is that you derive A -> B conversion rate from USD -> X converson rates only, and preventing each conversion to clash with another conversion, disallowing cycles completely.
