Scala: Filtering based on type

Question

I'm learning Scala as it fits my needs well but I am finding it hard to structure code elegantly. I'm in a situation where I have a List x and want to create two Lists: one containing all the elements of SomeClass and one containing all the elements that aren't of SomeClass.

val a = x collect {case y:SomeClass => y}
val b = x filterNot {_.isInstanceOf[SomeClass]}

Right now my code looks like that. However, it's not very efficient as it iterates x twice and the code somehow seems a bit hackish. Is there a better (more elegant) way of doing things?

It can be assumed that SomeClass has no subclasses.

Answer 1

Use list.partition:

scala> val l = List(1, 2, 3)
l: List[Int] = List(1, 2, 3)

scala> val (even, odd) = l partition { _ % 2 == 0 }
even: List[Int] = List(2)
odd: List[Int] = List(1, 3)

EDIT

For partitioning by type, use this method:

def partitionByType[X, A <: X](list: List[X], typ: Class[A]): 
    Pair[List[A], List[X]] = {
    val as = new ListBuffer[A]
    val notAs = new ListBuffer[X]
    list foreach {x =>
      if (typ.isAssignableFrom(x.asInstanceOf[AnyRef].getClass)) {
        as += typ cast x 
      } else {
        notAs += x
      }
    }
    (as.toList, notAs.toList)
}

Usage:

scala> val (a, b) = partitionByType(List(1, 2, "three"), classOf[java.lang.Integer])
a: List[java.lang.Integer] = List(1, 2)
b: List[Any] = List(three)

Answer 2

EDITED

While using plain partition is possible, it loses the type information retained by collect in the question.

One could define a variant of the partition method that accepts a function returning a value of one of two types using Either:

import collection.mutable.ListBuffer

def partition[X,A,B](xs: List[X])(f: X=>Either[A,B]): (List[A],List[B]) = {
  val as = new ListBuffer[A]
  val bs = new ListBuffer[B]
  for (x <- xs) {
    f(x) match {
      case Left(a) => as += a
      case Right(b) => bs += b
    }
  }
  (as.toList, bs.toList)
}

Then the types are retained:

scala> partition(List(1,"two", 3)) {
  case i: Int => Left(i)
  case x => Right(x)
}

res5: (List[Int], List[Any]) = (List(1, 3),List(two))

Of course the solution could be improved using builders and all the improved collection stuff :) .

For completeness my old answer using plain partition:

val (a,b) = x partition { _.isInstanceOf[SomeClass] }

For example:

scala> val x = List(1,2, "three")
x: List[Any] = List(1, 2, three)

scala> val (a,b) = x partition { _.isInstanceOf[Int] }
a: List[Any] = List(1, 2)
b: List[Any] = List(three)

Answer 3

If the list only contains subclasses of AnyRef, becaus of the method getClass. You can do this:

scala> case class Person(name: String)                                                           
defined class Person

scala> case class Pet(name: String)                                                              
defined class Pet

scala> val l: List[AnyRef] = List(Person("Walt"), Pet("Donald"), Person("Disney"), Pet("Mickey"))
l: List[AnyRef] = List(Person(Walt), Pet(Donald), Person(Disney), Pet(Mickey))

scala> val groupedByClass = l.groupBy(e => e.getClass)
groupedByClass: scala.collection.immutable.Map[java.lang.Class[_],List[AnyRef]] = Map((class Person,List(Person(Walt), Person(Disney))), (class Pet,List(Pet(Donald), Pet(Mickey))))

scala> groupedByClass(classOf[Pet])(0).asInstanceOf[Pet]
res19: Pet = Pet(Donald)

Answer 4

Just wanted to expand on mkneissl's answer with a "more generic" version that should work on many different collections in the library:

scala> import collection._
import collection._

scala> import generic.CanBuildFrom
import generic.CanBuildFrom

scala> def partition[X,A,B,CC[X] <: Traversable[X], To, To2](xs : CC[X])(f : X => Either[A,B])(
     |   implicit cbf1 : CanBuildFrom[CC[X],A,To], cbf2 : CanBuildFrom[CC[X],B,To2]) : (To, To2) = {
     |   val left = cbf1()
     |   val right = cbf2()
     |   xs.foreach(f(_).fold(left +=, right +=))
     |   (left.result(), right.result())
     | }
partition: [X,A,B,CC[X] <: Traversable[X],To,To2](xs: CC[X])(f: (X) => Either[A,B])(implicit cbf1: scala.collection.generic.CanBuildFrom[CC[X],A,To],implicit cbf2: scala.collection.generic.CanBuildFrom[CC[X],B,To2])(To, To2)

scala> partition(List(1,"two", 3)) {                                                                
     |   case i: Int => Left(i)                                                                     
     |   case x => Right(x)                                                                         
     | }
res5: (List[Int], List[Any]) = (List(1, 3),List(two))

scala> partition(Vector(1,"two", 3)) {
     |   case i: Int => Left(i)       
     |   case x => Right(x)           
     | }
res6: (scala.collection.immutable.Vector[Int], scala.collection.immutable.Vector[Any]) = (Vector(1, 3),Vector(two))

Just one note: The partition method is similar, but we need to capture a few types:

X -> The original type for items in the collection.

A -> The type of items in the left partition

B -> The type of items in the right partition

CC -> The "specific" type of the collection (Vector, List, Seq etc.) This must be higher-kinded. We could probably work around some type-inference issues (see Adrian's response here: http://suereth.blogspot.com/2010/06/preserving-types-and-differing-subclass.html ), but I was feeling lazy ;)

To -> The complete type of collection on the left hand side

To2 -> The complete type of the collection on the right hand side

Finally, the funny "CanBuildFrom" implicit paramters are what allow us to construct specific types, like List or Vector, generically. They are built into to all the core library collections.

Ironically, the entire reason for the CanBuildFrom magic is to handle BitSets correctly. Because I require CC to be higher kinded, we get this fun error message when using partition:

scala> partition(BitSet(1,2, 3)) {    
     |   case i if i % 2 == 0  => Left(i)
     |   case i if i % 2 == 1 => Right("ODD")
     | }
<console>:11: error: type mismatch;
 found   : scala.collection.BitSet
 required: ?CC[ ?X ]
Note that implicit conversions are not applicable because they are ambiguous:
 both method any2ArrowAssoc in object Predef of type [A](x: A)ArrowAssoc[A]
 and method any2Ensuring in object Predef of type [A](x: A)Ensuring[A]
 are possible conversion functions from scala.collection.BitSet to ?CC[ ?X ]
       partition(BitSet(1,2, 3)) {

I'm leaving this open for someone to fix if needed! I'll see if I can give you a solution that works with BitSet after some more play.