Remove all indices from collection

Question

Let's say I have a Scala collection of elements, and another collection of booleans, of the same size as the first collection (for the curious readers, the second collection is a result of Ramer-Douglas-Peucker algorithm).

Now I want to remove all the items from the first collection, where the second collection has false at the same index, in a single pass, without creating intermediate collections. I couldn't find any of the built-in methods on any of the Scala collections that can do it. Of course I can write my own, but I'm surprised Scala collections doesn't one already. Am I just missing it?

Example:

List(1, 2, 3).removeWhere(List(false, true, false)) shouldEqual List(2) 
// removeWhere is an imaginary name for the method I'm looking for

Answer 1

view processes elements one by one.

scala> val xs = List(1,2,3).view.zip(List(true,false,true)).collect{case (x, true) => x}
xs: scala.collection.SeqView[Int,Seq[_]] = SeqViewZFM(...)

scala> xs.head
res0: Int = 1

scala> xs.tail
res1: scala.collection.SeqView[Int,Seq[_]] = SeqViewZFMS(...)

Answer 2

I was bored and wrote the manual version:

def removeWhere_(l1 : List[Int], l2 : List[Boolean], acc : List[Int] => List[Int]) : List[Int] = {
    (l1, l2) match {
      case ( x::xs, y::ys ) if y => removeWhere_(xs,ys, f => acc(x :: f))
      case ( x::xs, y::ys)       => removeWhere_(xs,ys, f => acc(f) )
      case _ => acc(List())
    }
  }

def removeWhere(l1 : List[Int], l2 : List[Boolean]) = removeWhere_(l1, l2, x => x)

Not sure how much you lose from creating all the functors to allow for tail call optimization, but it's only one traversal.

Answer 3

I don't know whether this qualifies as "a single pass," but you could do:

val list1 = List(1, 2, 3)
val list2 = List(false, true, false)
val filtered = list1.filter(elem => list2(list1.indexOf(elem)))

However, the above is insufficient if list1 has duplicate elements.

Another way to do it, which probably violates your "single pass" requirement, is:

val filtered = list1.zip(list2).filter(_._2).map(_._1)

Answer 4

You can convert the List to its lazy counterpart, a Stream, and then use zip and filter:

List(1, 2, 3).toStream.zip(List(false, true, false)).filter(_._2).map(_._1).toList