Scala .zip with higher-kinded types, weird behaviour

Question

Following the question and answer in Scala methods and higher-kinded type parameters where I asked how to create a method with higher-kinded parameters so I could use any Seq, I am facing now a weird problem when using the .zip method. The code below doesn't compile, the complire reports:

Error:(18, 28) type mismatch;
 found   : Seq[X]
 required: S[X]
        itrA.zip(itrB).map {

I don't know where S[X] is transformed to Seq[X]. However, if I replace the code with the call to .zip with a more simple one (the commented one) which simply sums both heads of itrA and itrB and returns ItrA, the compilation is successful.

The code is:

object SeqOps {

  def sum[X: Numeric, S[Y] <: Seq[Y]](s: Seq[S[X]])
    (implicit cbf: CanBuildFrom[Nothing, X, S[X]]): Seq[X] =

  /*
      This code compiles
       s.reduce{(itrA, itrB) =>
          val num = implicitly[Numeric[X]]
          val sum = new num.Ops(itrA.head).+(itrB.head)
          itrA
          */

      s.reduce{(itrA, itrB) =>
        itrA.zip(itrB).map { // it seems that itrB loses the type here :/
          case (a, b) =>
            val num = implicitly[Numeric[X]]
            val sum = new num.Ops(a).+(b)
            sum
      }

  }

  def main(args: Array[String]): Unit = {
    sum(Seq(Vector(1), Vector(1)))
  }

}

The questions are: Why is this happening? How can I fix it?

Answer 1

It doesn't know that if you zip two S[X] that it can somehow build an S[(X, X)] out of it. For this to work, you need a CBF that knows how to build an S[(X, X)].

Unfortunately, there don't seem to be any implicits that would be able to build e.g. Vector[Int] out of a generic Seq[_], so you need more information about the type of the collection from which you're building. The idea is that traits with -Like name can provide this information. In this case, SeqLike[X, Repr] carries the Repr-type around.

If you now stare long enough at the signature of zip in SeqLike:

def zip
  [A1 >: A, B, That]
  (that: GenIterable[B])
  (implicit bf: CanBuildFrom[Repr, (A1, B), That])
: That

then you'll see that you can give it a CBF that has Repr in the first component. So you might try something like this (note with SeqLike and two CBFs - one for zip, another one for map):

import scala.collection.generic.CanBuildFrom
import scala.language.higherKinds
import scala.collection.SeqLike

object SeqOps {


  def sum[X: Numeric, S[Y] <: Seq[Y] with SeqLike[Y, S[Y]]]
    (s: Seq[S[X]])
    (implicit 
      cbf1: CanBuildFrom[S[_], X, S[X]],
      cbf2: CanBuildFrom[S[_], (X, X), S[(X, X)]]
    )
  : Seq[X] = {
    val num = implicitly[Numeric[X]]
    import num._
    s.reduce(_.zip(_)(cbf2).map{ case (a, b) => a + b })
  }


  def main(args: Array[String]): Unit = {
    println(sum(Seq(Vector(1), Vector(1))))     // Vector(2)
    println(sum(Seq(List(2, 3), List(4, 5))))   // List(6, 8)
  }

}

Another remark: In certain cases, it is easier to think of Nothing as of Unobtanium. If your CBF requires Unobtanium to build an S[X], it's probably not good for anything, because where do you want to get Unobtanium?