score:3

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

score:3

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.


Related Query

More Query from same tag