如何在Scala中从列表中删除对象的第一个出现？

Question

如何在Scala中从列表中删除对象的第一个出现？

作为Java程序员，我习惯于使用List.remove(Object o)方法来从列表中删除元素的第一个出现。现在我在使用Scala，我希望该方法返回一个新的不可变List而不是改变给定的列表。我还希望remove()方法采用谓词而不是对象。综合起来，我期望找到这样一个方法：

/**
 * 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]

当然，我可以用几种不同的方法自己实现这个方法，但是没有一种方法显然是最好的。我不想将我的列表转换为Java列表（甚至不是Scala可变列表），然后再转回来，虽然这肯定会起作用。我可以使用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)
}

然而，使用链表索引通常不是最高效的方式。

我可以编写一个更高效的方法，如下所示：

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

然而，那并不十分简洁。看起来很奇怪为什么没有现有的方法可以让我高效且简洁地完成此操作。那么，我是否遗漏了什么，或者我的最终方案确实是最好的？

- Joe Carnahan

---

开炮，我在提问之前搜索了这个问题一段时间，但是发帖后我只找到了一个重复的：https://dev59.com/r2035IYBdhLWcg3wE71s - Joe Carnahan

Answer 1

您可以使用 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集合API概述是学习一些不太常见的方法的好地方。

- retronym

---

但那不起作用。我认为你必须否定谓词。 - Debilski

val (before, _ :: after) = list span (x => !pred(x)) - Daniel C. Sobral

我认为drop(1)更好，因为它适用于atAndAfter == Nil的情况。 - incrop

Answer 2

这是一个小幅度可变性发挥大作用的案例:

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

这可以轻松地概括为删除与断言匹配的前n个元素。 (i<1 || { i = i-1; false })

你也可以自己编写过滤器，但是如果列表很长，使用这个版本将会导致堆栈溢出，因此现在几乎肯定更好地使用span函数。

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
}

而且其他东西比没有任何明显益处的span更加复杂。

- Rex Kerr

---

我不喜欢这个解决方案，因为即使found为真，过滤器仍会检查所有值。如果找到搜索的值，我更喜欢一个尾递归内部方法，它可以附加列表的尾部。 - kiritsuku

@Antoras - 对于列表的观点已经被接受。我已经展示了如何使用递归方法来完成它；我会把尾递归作为一个有动力的练习留给大家。 - Rex Kerr