How to return the original collection type from generic method

Question

I have a generic method that should return a collection of the same type as input:

def removeN[A, C <: Seq[A]](s: C, n: Int): C = {
  s.take(n) ++ s.drop(n + 1) // Sample operation
}

But this code does not compile:

Error:(34, 15) type mismatch; found : Seq[A] required: C s.take(n) ++ s.drop(n + 1)

1. How is this possible when C clearly stands for Seq[A]? Does it mean that this kind of concatenation always return an instance of parent type Seq[A], not a subtype C? Could my code be rewritten in order to produce a collection of type C?
2. Is this a correct way to define a generic method that returns the same collection type (in my case a subtype of Seq) as input in general?

Scala 2.12.4

Answer 1

What you're asking for can be done using one of the most powerful yet controversial features of the collections library, that is CanBuildFrom. Here is how:

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

def removeN[A, C[A] <: Seq[A]](s: C[A], n: Int)
  (implicit cbf: CanBuildFrom[C[A], A, C[A]]): C[A] = {
  val builder = cbf()
  builder.sizeHint(s.size)
  builder ++= s.take(n)
  builder ++= s.drop(n + 1)
  builder.result()
}

Let's give it a twist in the REPL:

scala> removeN(List(4, 5, 6), 2)
res0: List[Int] = List(4, 5)

scala> removeN(Vector(4, 5, 6), 2)
res1: scala.collection.immutable.Vector[Int] = Vector(4, 5)

It seems to work.

import scala.language.higherKinds is needed in order to avoid a warning for the higher-kind (C[A]) usage.