Scala collection filter by type

Question

Hi, im new to scala and ran into the following problem:

I want to get a subcollection of an existing collection that only contains elements of a specific type. The following works:

class C(val name : String)
class D(name : String) extends C(name) { }

val collection = Set[C](new C("C1"),new D("D1"),new C("C2"),new D("D2"))
collection.collect{case d : D => d}.size must be === 2 // works

But when i try to extend the collection classes with a method "onlyInstancesOf[Type]" this does not work. First my implementation:

object Collection {
    implicit def extendScalaCollection[E](coll : Traversable[E]) = new CollectionExtension[E](coll)
}

class CollectionExtension[E](coll : Traversable[E]) {

    def onlyInstancesOf[SpecialE <: E] : Traversable[SpecialE] = {
        coll.collect({case special : SpecialE => special}).asInstanceOf[Traversable[SpecialE]]
    }
}

So when i use this extension and execute:

collection.onlyInstancesOf[D].size must be === 2

I get an error that .size returned 4 and not 2. Also, i checked, the result actually contains C1 and C2 though it should not.

When i do:

collection.onlyInstancesOf[D].foreach(e => println(e.name))

I get the exception:

java.lang.ClassCastException: CollectionsSpec$$anonfun$1$C$1 cannot be cast to CollectionsSpec$$anonfun$1$D$1

So obviously the resulting set still contains the elements that should have been filtered out.

I dont get why this happens, can anyone explain this?

Edit: Scala: Scala code runner version 2.8.0.final

Answer 1

Pay attention to the compiler warnings, and add -unchecked your scala command line options.

M:\>scala -unchecked
Welcome to Scala version 2.8.0.final (Java HotSpot(TM) Client VM, Java 1.6.0_21)
.
Type in expressions to have them evaluated.
Type :help for more information.

scala> class CollectionExtension[E](coll : Traversable[E]) {
     |
     |     def onlyInstancesOf[SpecialE <: E] : Traversable[SpecialE] = {
     |         coll.collect({case special : SpecialE => special}).asInstanceOf[Traversable[SpecialE]]
     |     }
     | }
<console>:8: warning: abstract type SpecialE in type pattern SpecialE is unchecked since it is eliminated by erasure
               coll.collect({case special : SpecialE => special}).asInstanceOf[Traversable[SpecialE]]
                                            ^
defined class CollectionExtension

The warning means that the best the compiler can do is equivalent to:

coll.collect({case special : AnyRef => special}).asInstanceOf[Traversable[_]]

For a more detailed explanation of type erasure, and ways you can work around it with Manifests, see:

http://stackoverflow.com/questions/tagged/type-erasure+scala

Answer 2

Scala runs on the JVM, which unfortunately erases type parameters at runtime: http://en.wikipedia.org/wiki/Generics_in_Java#Type_erasure. In your first example, you give the type in a non-erased position and so the runtime code can do the comparison. In the second example, the SpecialE type is erased, and hence the code will return everything.

You can use scala's Manifests to regain some of the information lost by type erasure:

import scala.reflect.ClassManifest
class CollectionsExtension[E <: AnyRef](coll : Traversable[E]) {
  def onlyInstancesOf[SpecialE <: E](implicit m : Manifest[SpecialE]) : Traversable[SpecialE] = {
    coll.collect({case e if (ClassManifest.singleType(e) <:< m) => e}).asInstanceOf[Traversable[SpecialE]]
  }
}

Answer 3

As the warning say:

<console>:14: warning: abstract type SpecialE in type pattern SpecialE is unchecked since it is eliminated by erasure
               coll.collect({case special : SpecialE => special}).asInstanceOf[Traversable[SpecialE]]

Let's see the implementation of collect:

def collect[B, That](pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
  val b = bf(repr)
  for (x <- this) if (pf.isDefinedAt(x)) b += pf(x)
  b.result
}

Note that there's no pattern matching in here. This is the fundamental difference -- when you write "collection.collect{case d : D => d}" the compiler knows exactly what type you are talking about: D.

On the other hand, when you write coll.collect({case special : SpecialE => special}), the compiler doesn't know what type SpecialE, because SpecialE is just a type parameter. So it can't generate code that knows what SpecialE is, and, at run-time, there's no SpecialE anymore -- the bytecode just uses java.lang.Object.

Answer 4

As others have pointed out, manifests can rescue you. Here's an example of how, restricting ourselves to non-primitives, and assuming we don't want to store manifests in our collections but instead use reflection on the spot to figure things out:

class CollectionExtension[E <: AnyRef](coll : Traversable[E]) {
  def onlyInstancesOf[SpecialE <: E](implicit mf : Manifest[SpecialE]) : Traversable[SpecialE] = {
    coll.collect({
      case special if mf.erasure.isAssignableFrom(special.getClass) => special
    }).asInstanceOf[Traversable[SpecialE]]
  }
}

and here it is in action:

scala> val ce = new CollectionExtension(List(Some(1),Some(5),"This","Fox")) 
ce: CollectionExtension[java.lang.Object] = CollectionExtension@1b3d4787

scala> val opts = ce.onlyInstancesOf[Some[_]]
opts: Traversable[Some[_]] = List(Some(1), Some(5))

scala> val strings = ce.onlyInstancesOf[String] 
strings: Traversable[String] = List(This, Fox)