Scala - Co/Contra-Variance as applied to implicit parameter selection

Question

I've got a trait like this:

trait CanFold[-T, R] {
  def sum(acc: R, elem: T): R
  def zero: R
}

With a function that works with it like this:

def sum[A, B](list: Traversable[A])(implicit adder: CanFold[A, B]): B = 
  list.foldLeft(adder.zero)((acc,e) => adder.sum(acc, e))

The intention is to do something like this:

implicit def CanFoldSeqs[A] = new CanFold[Traversable[A], Traversable[A]] {
  def sum(x: Traversable[A], y: Traversable[A]) = x ++ y
  def zero = Traversable()
}

sum(List(1, 2, 3) :: List(4, 5) :: Nil)
//=> Traversable[Int] = List(1, 2, 3, 4, 5)

So it's a type-class for types for which the environment already knows how to fold and can be defined for Ints, Strings, whatever.

My problem is that I want to also have more-specific implicits that take priority, like this:

implicit def CanFoldSets[A] = new CanFold[Set[A], Set[A]] {
  def sum(x: Set[A], y: Set[A]) = x ++ y
  def zero = Set.empty[A]
}

sum(Set(1,2) :: Set(3,4) :: Nil)
//=> Set[Int] = Set(1, 2, 3, 4)

However that method call generates a conflict, as there's ambiguity:

both method CanFoldSeqs in object ...
and method CanFoldSets in object ...
match expected type CanFold[Set[Int], B]

So what I want is for the compiler to search for the most specific implicit between Any and my type. The intent is to provide default implementations for base types that can be overridden easily for more specific sub-types, without shadowing which is ugly.

I'm may be wishfully thinking here, but one can only hope :-)

Answer 1

The usual approach in a situation like this takes advantage of the way that implicits are prioritized by inheritance:

trait LowPriorityCanFoldInstances {
  implicit def CanFoldSeqs[A] = new CanFold[Traversable[A], Traversable[A]] {
    def sum(x: Traversable[A], y: Traversable[A]) = x ++ y
    def zero = Traversable()
  }
}

object CanFoldInstances extends LowPriorityCanFoldInstances {
  implicit def CanFoldSets[A] = new CanFold[Set[A], Set[A]] {
    def sum(x: Set[A], y: Set[A]) = x ++ y
    def zero = Set.empty[A]
  }
}

import CanFoldInstances._

Now the Set instance will be used when it's applicable, but the one for Traversable is still available when it's not.