How should I remove the first occurrence of an obj

Question

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

Coming from Java, I'm accustomed to having a List.remove(Object o) method that removes the first occurrence of an element from a list. Now that I'm working in Scala, I would expect the method to return a new immutable List instead of mutating a given list. I might also expect the remove() method to take 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 myself several different ways, but none of them jump out at me as being obviously the best. I would rather not convert my list to a Java list (or even to a Scala mutable list) and back again, although that would 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 indices with linked lists is usually not the most efficient way to go.

I can write a more efficient method like this:

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)
}

Still, that's not exactly succinct. It seems strange that there's not an existing method that would let me do this efficiently and succinctly. So, am I missing something, or is my last solution really as good as it gets?

Answer 1

You can clean up 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)

The Scala Collections API overview is a great place to learn about some of the lesser known methods.

Answer 2

This is a case where a little bit of mutability 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 dropping the first n items matching the predicate. (i<1 || { i = i-1; false })

You can also write the filter yourself, though at this point you're almost certainly 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 anything else is more complicated than span without any clear benefits.