How to avoid ambiguous conversion chains with multiple Type Class relationships?

Question

In my library, I have three type classes:

trait Monoid[T] {
  val zero : T
  def sum(x : T, y : T) : T
}

trait AbelianGroup[T] extends Monoid[T] {
  def inverse(x : T) : T
  def difference(x : T, y : T) : T
}

//represents types that are represents lists with a fixed number of elements, such as
//the tuple type (Int, Int)
trait Vector[T, U] {
  ...
}

These type classes are convertible to one another under the following conditions:

• If type T is a scala.math.Numeric type, it is also an AbelianGroup.
• If type T is an AbelianGroup, it is also a Monoid (currently, AbelianGroup extends Monoid, but that need not necessarily be the case)
• If type T is a Vector over type U, and type U is a Monoid, then type T is also a Monoid.
• If type T is a Vector over type U, and type U is a AbelianGroup, then T is also an AbelianGroup.

For example, since (Int, Int) is a Vector over type Int, and Int is an AbelianGroup, then (Int, Int) is also an AbelianGroup.

These relationships and others are easily implemented in the companion classes like so:

object Monoid {
  implicit def fromAbelianGroup[T : AbelianGroup] : Monoid[T] = implicitly[AbelianGroup[T]]
  implicit def fromVector[T : Vector[T, U], U : Monoid] : Monid[T] = ...
}

object AbelianGroup {
  implicit def fromNumeric[T : Numeric] : AbelianGroup[T] = ...
  implicit def fromOtherTypeX[T : ...] : AbelianGroup[T]
  ...
  implicit def fromVector[T : Vector[T, U], U : AbelianGroup] : AbelianGroup[T] = ...
}

This works out great until you try to use something like the tuple type (Int, Int) as a Monoid. The compiler finds two ways to get a Monoid type class object for such a type:

1. Monoid.fromAbelianGroup(AbelianGroup.fromVector(Vector.from2Tuple, AbelianGroup.fromNumeric))

2. Monoid.fromVector(Vector.from2Tuple, Monid.fromAbelianGroup(AbelianGroup.fromNumeric))

To resolve this ambiguity, I modified the Monoid companion class to include a direct conversion from Numeric (and other types directly convertible to AbelianGroup).

/*revised*/
object Monoid {
  //implicit def fromAbelianGroup[T : AbelianGroup] : Monoid[T] = implicitly[AbelianGroup[T]]
  implicit def fromNumeric[T : Numeric] : Monoid[T] = ... //<-- redundant
  implicit def fromOtherTypeX[T : ...] : AbelianGroup[T] = ... //<-- redundant
  ...
  implicit def fromVector[T : Vector[T, U], U : Monoid] : Monid[T] = ...
}

object AbelianGroup {
  implicit def fromNumeric[T : Numeric] : AbelianGroup[T] = ...
  implicit def fromOtherTypeX[T : ...] : AbelianGroup[T] = ...
  ...
  implicit def fromVector[T : Vector[T, U], U : AbelianGroup] : AbelianGroup[T] = ...
}

However, this is a bit unsatisfying, as it essentially violates the DRY principal. When I add new implementations for AbelianGroups, I would have to implement a conversion in both companion objects, just as I have done for Numeric and OtherTypeX, etc. So, I feel like I've taken a wrong turn somewhere.

Is there a way to revise my code to avoid this redundancy AND resolve the compile-time ambiguity error? What is the best practice in this kind of scenario?

Flop

Why do you need fromAbelianGroup? An AbelianGroup[T] already is a Monoid[T], and the compiler will provide one anywhere Monoid[T] is required. – Egregious

Because the compiler looks for possible conversions in Monoid's companion class, so without fromAbelianGroup, it won't find the conversion fromNumberic, etc. Also, if I import AbelianGroup's companion object at every call site so that it finds the conversions (something I really don't consider a satisfactory solution), the ambiguity will still exist even without fromAbelianGroup. – Flop

Can you post a gist with the code that doesn't compile (v1) ? – Ropy

Answer 1

You can move the implicits for which you want to have lower priority into a supertype of the companion object:

trait LowPriorityMonoidImplicits {
  implicit def fromVector[T : Vector[T, U], U : Monoid] : Monoid[T] = ...
}

object Monoid extends LowPriorityMonoidImplicits  {
  implicit def fromAbelianGroup[T : AbelianGroup] : Monoid[T] = implicitly[AbelianGroup[T]]
}

Copywriter