Как мне удалить первое вхождение объекта из списка в Scala? - PullRequest
Новая
       26

Как мне удалить первое вхождение объекта из списка в Scala?

4 голосов
/ 10 октября 2011

Каков наилучший способ удалить первое вхождение объекта из списка в 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)
}

Тем не менее, это не совсем лаконично.Кажется странным, что нет существующего метода, который позволил бы мне сделать это эффективно и кратко.Итак, я что-то упустил или мое последнее решение действительно так хорошо, как оно есть?

Ответы [ 2 ]

14 голосов
/ 10 октября 2011

Вы можете немного очистить код с помощью 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)

Обзор API Scala Collections - отличное место для изучения некоторых менее известных методов.

2 голосов
/ 10 октября 2011

Это случай, когда немного изменчивости имеет большое значение: 

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 без каких-либо явных преимуществ.

...