Mixing in generic traits in parameterized classes without duplicating type parameters

Question

Let's assume I want to create a trait that I can mix in into any Traversable[T]. In the end, I want to be able to say things like:

val m = Map("name" -> "foo") with MoreFilterOperations

and have methods on MoreFilterOperations that are expressed in anything Traversable has to offer, such as:

def filterFirstTwo(f: (T) => Boolean) = filter(f) take 2

However, the problem is clearly that T is not defined as a type parameter on MoreFilterOperations. Once I do that, it's doable of course, but then my code would read:

val m = Map("name" -> "foo") with MoreFilterOperations[(String,String)]

or if I define a variable of this type:

var m2: Map[String,String] with MoreFilterOperations[(String,String)] = ...

which is way to verbose for my taste. I would like to have the trait defined in such a way that I could write the latter as:

var m2: Map[String,String] with MoreFilterOperations

I tried self types, abstract type members, but it hasn't resulted in anything useful. Any clues?

Answer 1

Map("name" -> "foo") is a function invocation and not a constructor, this means that you can't write:

Map("name" -> "foo") with MoreFilterOperations

any more that you can write

val m = Map("name" -> "foo")
val m2 = m with MoreFilterOperations

To get a mixin, you have to use a concrete type, a naive first attempt would be something like this:

def EnhMap[K,V](entries: (K,V)*) =
  new collection.immutable.HashMap[K,V] with MoreFilterOptions[(K,V)] ++ entries

Using a factory method here to avoid having to duplicate the type params. However, this won't work, because the ++ method is just going to return a plain old HashMap, without the mixin!

The solution (as Sam suggested) is to use an implicit conversion to add the pimped method. This will allow you to transform the Map with all the usual techniques and still be able to use your extra methods on the resulting map. I'd normally do this with a class instead of a trait, as having constructor params available leads to a cleaner syntax:

class MoreFilterOperations[T](t: Traversable[T]) {
  def filterFirstTwo(f: (T) => Boolean) = t filter f take 2
}

object MoreFilterOperations {
  implicit def traversableToFilterOps[T](t:Traversable[T]) =
    new MoreFilterOperations(t)
}

This allows you to then write

val m = Map("name"->"foo", "name2"->"foo2", "name3"->"foo3")
val m2 = m filterFirstTwo (_._1.startsWith("n"))

But it still doesn't play nicely with the collections framework. You started with a Map and ended up with a Traversable. That isn't how things are supposed to work. The trick here is to also abstract over the collection type using higher-kinded types

import collection.TraversableLike

class MoreFilterOperations[Repr <% TraversableLike[T,Repr], T] (xs: Repr) {
  def filterFirstTwo(f: (T) => Boolean) = xs filter f take 2
}

Simple enough. You have to supply Repr, the type representing the collection, and T, the type of elements. I use TraversableLike instead of Traversable as it embeds its representation; without this, filterFirstTwo would return a Traversable regardless of the starting type.

Now the implicit conversions. This is where things get a bit trickier in the type notation. First, I'm using a higher-kinded type to capture the representation of the collection: CC[X] <: Traversable[X], this parameterises the CC type, which must be a subclass of Traversable (note the use of X as a placeholder here, CC[_] <: Traversable[_] does not mean the same thing).

There's also an implicit CC[T] <:< TraversableLike[T,CC[T]], which the compiler uses to statically guarantee that our collection CC[T] is genuinely a subclass of TraversableLike and so a valid argument for the MoreFilterOperations constructor:

object MoreFilterOperations {
  implicit def traversableToFilterOps[CC[X] <: Traversable[X], T]
  (xs: CC[T])(implicit witness: CC[T] <:< TraversableLike[T,CC[T]]) =
    new MoreFilterOperations[CC[T], T](xs)
}

So far, so good. But there's still one problem... It won't work with maps, because they take two type parameters. The solution is to add another implicit to the MoreFilterOperations object, using the same principles as before:

implicit def mapToFilterOps[CC[KX,VX] <: Map[KX,VX], K, V]
(xs: CC[K,V])(implicit witness: CC[K,V] <:< TraversableLike[(K,V),CC[K,V]]) =
  new MoreFilterOperations[CC[K,V],(K,V)](xs)

The real beauty comes in when you also want to work with types that aren't actually collections, but can be viewed as though they were. Remember the Repr <% TraversableLike in the MoreFilterOperations constructor? That's a view bound, and permits types that can be implicitly converted to TraversableLike as well as direct subclasses. Strings are a classic example of this:

implicit def stringToFilterOps
(xs: String)(implicit witness: String <%< TraversableLike[Char,String])
: MoreFilterOperations[String, Char] =
  new MoreFilterOperations[String, Char](xs)

If you now run it on the REPL:

val m = Map("name"->"foo", "name2"->"foo2", "name3"->"foo3")
//  m: scala.collection.immutable.Map[java.lang.String,java.lang.String] =
//    Map((name,foo), (name2,foo2), (name3,foo3))

val m2 = m filterFirstTwo (_._1.startsWith("n"))
//  m2: scala.collection.immutable.Map[java.lang.String,java.lang.String] =
//    Map((name,foo), (name2,foo2))

"qaxfwcyebovjnbointofm" filterFirstTwo (_ < 'g')
//res5: String = af

Map goes in, Map comes out. String goes in, String comes out. etc...

I haven't tried it with a Stream yet, or a Set, or a Vector, but you can be confident that if you did, it would return the same type of collection that you started with.

Answer 2

It's not quite what you asked for, but you can solve this problem with implicits:

trait MoreFilterOperations[T] {
  def filterFirstTwo(f: (T) => Boolean) = traversable.filter(f) take 2
  def traversable:Traversable[T]
}

object FilterImplicits {
  implicit def traversableToFilterOps[T](t:Traversable[T]) = new MoreFilterOperations[T] { val traversable = t }
}

object test {

  import FilterImplicits._

  val m = Map("name" -> "foo", "name2" -> "foo2", "name3" -> "foo3")
  val r = m.filterFirstTwo(_._1.startsWith("n"))
}

scala> test.r
res2: Traversable[(java.lang.String, java.lang.String)] = Map((name,foo), (name2,foo2))