Scala: найти и обновить один элемент в списке - PullRequest
Новая
       37

Scala: найти и обновить один элемент в списке

0 голосов
/ 03 января 2019

Я пытаюсь найти элегантный способ сделать: 

val l = List(1,2,3)

val (item, idx) = l.zipWithIndex.find(predicate)

val updatedItem = updating(item)

l.update(idx, updatedItem)

Можно ли сделать все за одну операцию?Найдите элемент, если он существует, замените его обновленным значением и сохраните его на месте.

Я мог бы сделать: 

l.map{ i => 
  if (predicate(i)) {
     updating(i)
  } else {
     i
  }
}

но это довольно уродливо.

Другая сложность заключается в том, что я хочу обновить только первый элемент, который соответствует predicate.

Редактировать: Попытка: 

implicit class UpdateList[A](l: List[A]) {
  def filterMap(p: A => Boolean)(update: A => A): List[A] = {
    l.map(a => if (p(a)) update(a) else a)
  }

  def updateFirst(p: A => Boolean)(update: A => A): List[A] = {
    val found = l.zipWithIndex.find { case (item, _) => p(item) }
    found match {
      case Some((item, idx)) => l.updated(idx, update(item))
      case None => l
    }
  }
}

Ответы [ 2 ]

0 голосов
/ 03 января 2019

Я не знаю способа сделать это за один проход коллекции без использования изменяемой переменной.С двумя проходами вы можете сделать это, используя foldLeft, как в: 

def updateFirst[A](list:List[A])(predicate:A => Boolean, newValue:A):List[A] = {
   list.foldLeft((List.empty[A], predicate))((acc, it) => {acc match {
     case (nl,pr) => if (pr(it)) (newValue::nl, _ => false) else (it::nl, pr)
   }})._1.reverse
}

Идея состоит в том, что foldLeft позволяет передавать дополнительные данные через итерацию.В этой конкретной реализации я изменяю предикат на фиксированный, который всегда возвращает false.К сожалению, вы не можете построить List из головы эффективным способом, поэтому для этого требуется еще один проход для reverse.

. Я считаю, что очевидно, как сделать это, используя комбинацию map иvar

Примечание : производительность List.map такая же, как и при одном проходе по списку, только потому, что внутренняя стандартная библиотека является изменчивой.В частности, класс cons :: объявлен как 

final case class ::[B](override val head: B, private[scala] var tl: List[B]) extends List[B] {

, поэтому tl на самом деле var, и это используется реализацией map для эффективного построения списка из головы.,Поле равно private[scala], поэтому вы не можете использовать тот же трюк за пределами стандартной библиотеки.К сожалению, я не вижу других API-вызовов, позволяющих использовать эту функцию, чтобы уменьшить сложность вашей проблемы за один проход.

0 голосов
/ 03 января 2019

Вы можете избежать .zipWithIndex(), используя .indexWhere().

Чтобы улучшить сложность, используйте Vector, чтобы l(idx) фактически становилось постоянным. 

val l = Vector(1,2,3)
val idx = l.indexWhere(predicate)
val updatedItem = updating(l(idx))
l.updated(idx, updatedItem)

Причина использования scala.collection.immutable.Vector вместо List: Scala's List - это связанный список, что означает доступ к данным за O (n) раз. Вектор Scala индексируется, что означает, что данные могут быть прочитаны из любой точки за фактически постоянное время.

Вы также можете рассмотреть изменчивые коллекции, если вы изменяете только один элемент в очень большой коллекции.

https://docs.scala -lang.org / обзоры / коллекции / производительность characteristics.html

...