CODEWITHSUNDEEP
scalascala-collections
gang
gang

Reputation: 55

Scala how to update values in immutable list

I have a immutable list and need a new copy of it with elements replaced at multiple index locations. The List.updated is an O(n) operation and can only replace one at a time. What is the efficient way of doing this? Thanks!

Upvotes: 2

Views: 2692

Answers (2)

Gabriele Petronella
Gabriele Petronella

Reputation: 108101

List is not a good fit if you need random element access/update. From the documentation:

This class is optimal for last-in-first-out (LIFO), stack-like access patterns. If you need another access pattern, for example, random access or FIFO, consider using a collection more suited to this than List.

More generally, what you need is an indexed sequence instead of a linear one (such as List). From the documentation of IndexedSeq:

Indexed sequences support constant-time or near constant-time element access and length computation. They are defined in terms of abstract methods apply for indexing and length.

Indexed sequences do not add any new methods to Seq, but promise efficient implementations of random access patterns.

The default concrete implementation of IndexedSeq is Vector, so you may consider using it.

Here's an extract from its documentation (emphasis added):

Vector is a general-purpose, immutable data structure. It provides random access and updates in effectively constant time, as well as very fast append and prepend. Because vectors strike a good balance between fast random selections and fast random functional updates, they are currently the default implementation of immutable indexed sequences

Upvotes: 7

Dima
Dima

Reputation: 40500

list
    .iterator
    .zipWithIndex
    .map { case (index, element) => newElementFor(index) }
    .toList

Upvotes: -2

Related Questions