How to remove the first occurrence of an object from a list in Scala?

Question

What is the best way to remove the first occurrence of an object from a list in Scala?

Starting in Java, I'm used to having a List.remove(Object o) method that removes the first occurrence of an item from a list. Now that I am working in Scala, I expect the method to return a new immutable List instead of mutating the given list. I can also expect the remove() method to use a predicate instead of an object. Taken together, I would expect to find a method like this:

 /** * Removes the first element of the given list that matches the given * predicate, if any. To remove a specific object <code>x</code> from * the list, use <code>(_ == x)</code> as the predicate. * * @param toRemove * a predicate indicating which element to remove * @return a new list with the selected object removed, or the same * list if no objects satisfy the given predicate */ def removeFirst(toRemove: E => Boolean): List[E] 

Of course, I can implement this method for myself in several different ways, but none of them jumps at me, as the fact that it is obviously the best. I would prefer not to convert my list to a Java list (or even to a Scala variable list) and vice versa, although this will certainly work. I could use List.indexWhere(p: (A) ⇒ Boolean) :

 def removeFirst[E](list: List[E], toRemove: (E) => Boolean): List[E] = { val i = list.indexWhere(toRemove) if (i == -1) list else list.slice(0, i) ++ list.slice(i+1, list.size) } 

However, using indexes with linked lists is usually not the most efficient way.

I can write a more efficient method:

 def removeFirst[T](list: List[T], toRemove: (T) => Boolean): List[T] = { def search(toProcess: List[T], processed: List[T]): List[T] = toProcess match { case Nil => list case head :: tail => if (toRemove(head)) processed.reverse ++ tail else search(tail, head :: processed) } search(list, Nil) } 

However, this is not entirely concise. It seems strange that there is no existing method that would allow me to do this efficiently and concisely. So, am I missing something, or is my last solution really as good as it gets?

Answer 1

You can clear the code a bit with span .

 scala> def removeFirst[T](list: List[T])(pred: (T) => Boolean): List[T] = { | val (before, atAndAfter) = list span (x => !pred(x)) | before ::: atAndAfter.drop(1) | } removeFirst: [T](list: List[T])(pred: T => Boolean)List[T] scala> removeFirst(List(1, 2, 3, 4, 3, 4)) { _ == 3 } res1: List[Int] = List(1, 2, 4, 3, 4) 

Scala Collection API Overview is a great place to learn about some of the lesser known methods.

Answer 2

This is the case when a little volatility goes a long way:

 def withoutFirst[A](xs: List[A])(p: A => Boolean) = { var found = false xs.filter(x => found || !p(x) || { found=true; false }) } 

This is easily generalized to removing the first elements of n corresponding to the predicate. ( i<1 || { i = i-1; false } )

You can also write the filter yourself, although at this point you will almost certainly be better off using span , since this version will overflow the stack if the list is long:

 def withoutFirst[A](xs: List[A])(p: A => Boolean): List[A] = xs match { case x :: rest => if (p(x)) rest else x :: withoutFirst(rest)(p) case _ => Nil } 

and everything else is more complicated than span without any obvious advantages.