Return a generic Traversable of a specified type

Question

I'd like to be able to generically manipulate types like T[_] <: Traversable so that I can do things like map and filter, but I'd like to defer the decision about which Traversable I select for as long as possible.

I'd like to be able write functions against a generic T[Int] that return a T[Int] not a Traversable[Int]. So for example, I'd like to apply a function to a Set[Int] or a Vector[Int] or anything that extends Traversable and get that type back.

I first attempted to do this in a simple manner like:

trait CollectionHolder[T[_] <: Traversable[_]] {

  def easyLessThanTen(xs: T[Int]): T[Int] = {
    xs.filter(_ < 10)
  }
}

but this won't compile: Missing parameter type for expanded function. It will compile, however, if the function takes a Traversable[Int] instead of a T[Int], so thought I could work with Traversable and convert to a T. This lead me to CanBuildFrom

object DoingThingsWithTypes {    

  trait CollectionHolder[T[_] <: Traversable[_]] {

    def lessThanTen(xs: T[Int])(implicit cbf: CanBuildFrom[Traversable[Int], Int, T[Int]]): T[Int] = {

      val filteredTraversable = xs.asInstanceOf[Traversable[Int]].filter(_ < 10)

      (cbf() ++= filteredTraversable).result
}

which compiles. But then in my tests:

val xs = Set(1, 2, 3, 4, 1000)

object withSet extends CollectionHolder[Set]

withSet.lessThanTen(xs) shouldBe Set(1, 2, 3, 4)

I get the following compiler error:

Cannot construct a collection of type Set[Int] with elements of type Int based on a collection of type Traversable[Int]. not enough arguments for method lessThanTen: (implicit cbf: scala.collection.generic.CanBuildFrom[Traversable[Int],Int,Set[Int]])Set[Int]. Unspecified value parameter cbf.

Where can I get a CanBuildFrom to make this conversion? Or better yet, how can I modify my simpler approach for the result I want? Or do I need to use a typeclass and write an implicit implementation for each Traversable I'm interested in using (one for Set, one for Vector etc)? I'd prefer to avoid the last approach if possible.

Answer 1

Using the (Scala 2.12.8) standard library instead of cats/scalaz/etc. you need to look at GenericTraversableTemplate. filter isn't defined there, but can easily be:

import scala.collection.GenTraversable
import scala.collection.generic.GenericTraversableTemplate

trait CollectionHolder[T[A] <: GenTraversable[A] with GenericTraversableTemplate[A, T]] {

  def lessThanTen(xs: T[Int]): T[Int] = {
    filter(xs)(_ < 10)
  }

  def filter[A](xs: T[A])(pred: A => Boolean) = {
    val builder = xs.genericBuilder[A]
    xs.foreach(x => if (pred(x)) { builder += x })
    builder.result()
  }
}

In the comment you mention nonEmpty and exists; they are available because of the GenTraversable type bound. Really filter is too, the problem is that it returns GenTraversable[A] instead of T[A].

Scala 2.13 reworks collections so the methods will probably be slightly different there, but I haven't looked enough at it yet.

Also: T[_] <: Traversable[_] is likely not what you want as opposed to T[A] <: Traversable[A]; e.g. the first constraint is not violated if you have T[Int] <: Traversable[String].