title: How should I remove the first occurrence of an object from a list in Scala?
body: <p>What is the best way to remove the first occurrence of an object from a list in Scala?</p>
  
  <p>Coming from Java, I'm accustomed to having a <a href="http://download.oracle.com/javase/7/docs/api/java/util/List.html#remove(java.lang.Object)" rel="noreferrer"><code>List.remove(Object o)</code></a> 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 <code>List</code> instead of mutating a given list.  I might also expect the <code>remove()</code> method to take a predicate instead of an object.  Taken together, I would expect to find a method like this:</p>
  
  <pre><code>/**
   * Removes the first element of the given list that matches the given
   * predicate, if any.  To remove a specific object &lt;code&gt;x&lt;/code&gt; from
   * the list, use &lt;code&gt;(_ == x)&lt;/code&gt; 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 =&gt; Boolean): List[E]
  </code></pre>
  
  <p>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 <code>List.indexWhere(p: (A) ⇒ Boolean)</code>:</p>
  
  <pre><code>def removeFirst[E](list: List[E], toRemove: (E) =&gt; Boolean): List[E] = {
    val i = list.indexWhere(toRemove)
    if (i == -1)
      list
    else
      list.slice(0, i) ++ list.slice(i+1, list.size)
  }
  </code></pre>
  
  <p>However, using indices with linked lists is usually not the most efficient way to go.</p>
  
  <p>I can write a more efficient method like this:</p>
  
  <pre><code>def removeFirst[T](list: List[T], toRemove: (T) =&gt; Boolean): List[T] = {
    def search(toProcess: List[T], processed: List[T]): List[T] =
      toProcess match {
        case Nil =&gt; list
        case head :: tail =&gt;
          if (toRemove(head))
            processed.reverse ++ tail
          else
            search(tail, head :: processed)
      }
    search(list, Nil)
  }
  </code></pre>
  
  <p>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?</p>