Why is the type information lost when calling collect on this higher-kinded type?

Question

I am trying to get familiar with higher-kinded types in Scala and so I tried implementing this simple method that takes a traversable of Option and flattens it just like flattening it normally would. However, the compiler is raising an error because the function returns type Traversable[Any] instead of T[S]. Why is this, and how can I make it work correctly?

def flatten[S, T[_] <: Traversable[_]](list: T[Option[S]]): T[S] = {
  list.collect({ case Some(s) => s })
}

I think that maybe I'm defining the type of T incorrectly, but I also tried T[_]: Traversable and T[X] <: Traversable[X] and those didn't work either.

Of course, this works:

def flatten[S](list: Traversable[Option[S]]): Traversable[S] = {
  list.collect({ case Some(s) => s })
}

But I don't want to lose the input type information on the return type (calling flatten(List[Option[T]]) should return List[T].

Answer 1

This is because collect doesn't return a T, it returns only a Traversable. The trait Traversable doesn't know the type of whatever class is inheriting it.

Furthermore, your higher-kinded type is wrong, it should be T[x] <: Traversable[x] to avoid weirdness with existentials. You could do something like this:

def flatten[S, T[x] <: Traversable[x]](list: T[Option[S]])(
  implicit ev: collection.generic.CanBuildFrom[Traversable[Option[S]], S, T[S]]
): T[S] = list.collect { case Some(s) => s }

, or you might be better off with Luis Miguel Mejía Suárez's suggestion of using typeclasses. I would also suggest using Scala 2.13 if possible.

trait Flatten[F[_]] {
  def flatten[S](list: F[Option[S]]): F[S]
}
object Flatten {
  def flatten[S, F[_]](list: List[Option[S]])(implicit f: Flatten[F]) = f.flatten(list)
  
  implicit val flattenList = new Flatten[List] {
    def flatten[S](list: List[Option[S]]) = list.collect { case Some(s) => s }
  }
}