Returning original collection type in generic method

Question

Say we want to make a function like minBy that returns all elements of equal minimalism in a collection:

def multiMinBy[A, B: Ordering](xs: Traversable[A])(f: A => B) = {
  val minVal = f(xs minBy f)
  xs filter (f(_) == minVal)
}

scala> multiMinBy(List("zza","zzza","zzb","zzzb"))(_.last)
res33: Traversable[java.lang.String] = List(zza, zzza)

So far, so good, except that we have a Traversable back instead of our initial List.

So I tried changing the signature to

def multiMinBy[A, B: Ordering, C <: Traversable[A]](xs: C)(f: A => B)

in the hope I might get a C back rather than a Traversable[A]. However, I don't get anything back:

scala> multiMinBy(List("zza","zzza","zzb","zzzb"))(_.last)

<console>:9: error: inferred type arguments [Nothing,Nothing,List[java.lang.String]] 
do not conform to method multiMinBy's type parameter bounds [A,B,C <: Traversable[A]]

I think this is because we have C appearing in the arguments before A has been inferred? So I flipped the order of the arguments, and added a cast:

def multiMinBy[A, B: Ordering, C <: Traversable[A]](f: A => B)(xs: C) = {
  val minVal = f(xs minBy f)
  (xs filter (f(_) == minVal)).asInstanceOf[C]
}

which works, except we have to call it like this:

multiMinBy((x: String) => x.last)(List("zza","zzza","zzb","zzzb"))

Is there a way to retain the original syntax, while getting the right collection type back?

Answer 1

I think Miles Sabin solution is way too complex. Scala's collection already have the necessary machinery to make it work, with a very small change:

import scala.collection.TraversableLike
def multiMinBy[A, B: Ordering, C <: Traversable[A]]
              (xs: C with TraversableLike[A, C])
              (f: A => B): C = {
  val minVal = f(xs minBy f)
  xs filter (f(_) == minVal)
}

Answer 2

How about using CanBuildFrom?

import scala.collection.immutable._
import scala.collection.generic._

def multiMinBy[A, B, From[X] <: Traversable[X], To](xs: From[A])(f: A => B)
  (implicit ord: Ordering[B], bf: CanBuildFrom[From[_], A, To])  = {
  val minVal = f(xs minBy f)
  val b = bf()
  b ++= (xs filter (f(_) == minVal))
  b.result
} 



scala> multiMinBy(List("zza","zzza","zzb","zzzb"))(_.last)
res1: List[java.lang.String] = List(zza, zzza)

Answer 3

Your problem is that when viewed as a method on GenTraversable[A] (which I'll use instead of Traversable[A] in this answer) the result type of the filter method is no more precise than GenTraversable[A]. Unfortunately within the body of the multiMinBy method as written that's all you know about xs.

To get the result you're after you'll have to make the signature of multiMinBy more precise. One way of doing this while still leaving the container type relatively open is to use a structural type as follows,

type HomFilter[CC[X] <: GenTraversable[X], A] = 
  CC[A] { def filter(p : A => Boolean) : CC[A] }

def multiMinBy[CC[X] <: GenTraversable[X], A, B: Ordering]
  (xs: HomFilter[CC, A])(f: A => B) : CC[A] = {
    val minVal = f(xs minBy f)
    xs filter (f(_) == minVal)
  }

The structural type HomFilter allows us to assert that the argument to multiMinBy must have a filter method with the desired result type.

Sample REPL session,

scala> val mmb = multiMinBy(List("zza","zzza","zzb","zzzb"))(_.last)
mmb: List[String] = List(zza, zzza)

Bear in mind that this is a stricter requirement than that the container just be Traversable: it's permissible for subtypes of GenTraversable to define filter methods which aren't regular in this way. The signature above will statically prevent values of such types from being passed to multiMinBy ... presumably that's the behaviour you're after.