Problems with contravariance in Scala

Question

I want to define a type-class like this:

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

implicit object CanFoldInts extends CanFold[Int, Int] {
  def sum(x: Int, y: Int) = x + y
  def zero = 0
}

implicit object CanFoldSeqs extends CanFold[Traversable[_], Traversable[_]] {
  def sum(x: Traversable[_], y: Traversable[_]) = x ++ y
  def zero = Traversable()
}

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

However, the problem is when I do this I get a Traversable[Any] and it would be nice to get a Traversable[Int] instead:

 scala> sum(List(1,2,3) :: List(4, 5) :: Nil)
 res10: Traversable[Any] = List(1, 2, 3, 4, 5)

To make matters worse, I cannot define an implicit for Traversable[Int] after defining one for Traversable[_], because then the definitions would cause ambiguity. After pulling my hair out I gave up.

Is there any way I could make that sum return a Traversable[T] instead of a Traversable[Any]?

Looking at how sum() is defined on Seq in Scala's library, I can see it works with Numeric, which is invariant, but I want default implementations for supertypes and having the result be different than the input (same as the fold operation) is nice.

Answer 1

The only way I know to add type parameters to such type classes is to use a def instead of an object:

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

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