Scala: Find and update one element in a list

user_3357831 0
Viewed 2366

I am trying to find an elegant way to do: 

val l = List(1,2,3)

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

val updatedItem = updating(item)

l.update(idx, updatedItem)

Can I do all in one operation ? Find the item, if it exist replace with updated value and keep it in place.

I could do: 

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

but that's pretty ugly.

The other complexity is the fact that I want to update only the first element which match predicate .

Edit: Attempt:

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
    }
  }
}
scalaz scala functional-programming
2 Answers

You can avoid .zipWithIndex() by using .indexWhere().

To improve complexity, use Vector so that l(idx) becomes effectively constant time.

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

Reason for using scala.collection.immutable.Vector rather than List: Scala's List is a linked list, which means data are access in O(n) time. Scala's Vector is indexed, meaning data can be read from any point in effectively constant time.

You may also consider mutable collections if you're modifying just one element in a very large collection.

https://docs.scala-lang.org/overviews/collections/performance-characteristics.html

user_108568520

I don't know any way to make this in one pass of the collection without using a mutable variable. With two passes you can do it using foldLeft as in:

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
}

The idea is that foldLeft allows passing additional data through iteration. In this particular implementation I change the predicate to the fixed one that always returns false. Unfortunately you can't build a List from the head in an efficient way so this requires another pass for reverse.

I believe it is obvious how to do it using a combination of map and var

Note: performance of the List.map is the same as of a single pass over the list only because internally the standard library is mutable. Particularly the cons class :: is declared as

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

so tl is actually a var and this is exploited by the map implementation to build a list from the head in an efficient way. The field is private[scala] so you can't use the same trick from outside of the standard library. Unfortunately I don't see any other API call that allows to use this feature to reduce the complexity of your problem to a single pass.

user_1826600
Related