Scala generics: covariance/contravariance in two-level data structure

Question

I have an algorithm that operates on indexed sequences of some objects: it gets two such sequences and should output one resulting sequence. I'd like it to be able to work with at least:

• Characters in a string
• Lines (strings) in array of text

For simplicity sake, let's assume that this algorithm just constructs a new sequence of objects, getting objects one-by-one from each of original sequences. There are some special cases when I have to return either empty sequence of objects of desired type or original objects. The only two operations I would use on original sequences are:

• getting i-th element by index
• getting size of sequence

My current code looks like this:

class GenericTest[C, T <: IndexedSeq[C]](a: T, b: T) {
  def run: T = {
    // special case #1: need to return empty sequence here
    if (a.size == 0) {
      // what I've tried:

      return new T()
      // fails: "class type required but T found"

      return Seq[C]()
      // fails: "type mismatch; found : Seq[C] required: T"

      return Array[C]()
      // fails: "not enough arguments for method apply: (implicit
      // evidence$2: scala.reflect.ClassTag[C])Array[C] in object
      // Array. Unspecified value parameter evidence$2."

      return Array.ofDim[C](0)
      // fails: "No ClassTag available for C"
      // "not enough arguments for method ofDim: (implicit
      // evidence$3: scala.reflect.ClassTag[C])Array[C].
      // Unspecified value parameter evidence$3."
    }

    // special case #2: need to return original input here
    if (a == b) {
      return a
      // it works
    }

    val result = new MutableList[C]

    for (i <- 0 until scala.math.min(a.size, b.size)) {
      result += a(i)
      result += b(i)
    }

    // what I've tried:

    return result
    // fails: "type mismatch; found : result.type (with underlying
    // type scala.collection.mutable.MutableList[C]) required: T"

    return result.toIndexedSeq
    // fails: "type mismatch; found : scala.collection.immutable.IndexedSeq[C]
    // required: T"
  }
}

So, basically, question is - how do I properly set up Scala generics for this task to be able to:

• Return empty sequence of objects
• Return constructed sequence of objects
• Return original input

I guess this question calls for covariance/contravariance annotations for type, my covariance-fu seems to be lacking...

Answer 1

Since lists in scala are covariant, you can add any object to the list as long as it is a subtype of the type of the list.

   class GenericTest[C](a: IndexedSeq[C], b: IndexedSeq[C]) {
      def run: IndexedSeq[C] = {
        // special case #1: need to return empty sequence here
        if (a.size == 0) {
          return IndexedSeq.empty[C]
        }

        // special case #2: need to return original input here
        if (a == b) {
          return a
        }

        val result = mutable.ArrayBuffer[C]()

        for (i <- 0 until scala.math.min(a.size, b.size)) {
          result += a(i)
          result += b(i)
        }
        result.toIndexedSeq
      }
    }