Immutable DataStructures In Scala

Question

We know that Scala supports immutable data structures..i.e each time u update the list it will create a new object and reference in the heap.

Example

val xs:List[Int] = List.apply(22)
val newList = xs ++ (33)

So when i append the second element to a list it will create a new list which will contain both 22 and 33.This exactly works like how immutable String works in Java. So the question is each time I append a element in the list a new object will be created each time..This ldoes not look efficient to me. is there some special data structures like persistent data structures are used when dealing with this..Does anyone know about this?

There are good reasons to favor immutability. A good summary of those reasons can be found in Effective Java, Item 15. As a solution to the performance problem, it suggests that you either rely on the efficient internal implementation of the mutable data structure, or use a mutable counterpart (e.g., ListBuffer). — Kulu Limpa
– Kulu Limpa, Commented Nov 19, 2014 at 13:27
List is only efficient when prepending. When you want to append, use an IndexedSeq, which uses a Vector data structure. That is reasonably efficient for both appending and prepending, and also immutable. — Rüdiger Klaehn
– Rüdiger Klaehn, Commented Nov 20, 2014 at 7:24

manojlds · Accepted Answer · 2014-11-19 12:59:08Z

1

Appending to a list has O(n) complexity and is inefficient. A general approach is to prepend to a list while building it, and finally reverse it.

Now, your question on creating new object still applies to the prepend. Note that since xs is immutable, newList just points to xs for the rest of the data after the prepend.

edited Nov 19, 2014 at 12:59

answered Nov 19, 2014 at 12:49

manojlds

303k66 gold badges482 silver badges426 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Vivek Patil Linksys3966 Over a year ago

Exactly but the question is that it can point for the rest of the data until the data is not changed.Say for example I have a list as val list = List(12,13,14) and I append one element say 15 to the immutable list i.e (list1 = list + 15) it will not create the new list.It will use the previous linkedlist and the pointer will point to the address of start i.e 12 and will create a new node for 15.But as soon as I change the data using the list reference it will create a new list for list1 to use(i.e copy the previous data) and modify the list reference.This is called persistent data structures.

Bob Dalgleish · Accepted Answer · 2014-11-19 13:15:27Z

1

While @manojlds is correct in his analysis, the original post asked about the efficiency of duplicating list nodes whenever you do an operation.

As @manojlds said, constructing lists often require thinking backwards, i.e., building a list and then reversing it. There are a number of other situations where list building requires "needless" copying.

To that end, there is a mutable data structure available in Scala called ListBuffer which you can use to build up your list and then extract the result as an immutable list:

val xsa = ListBuffer[Int](22)
xsa += 33
val newList = xsa.toList

However, the fact that the list data structure is, in general, immutable means that you have some very useful tools to analyze, de-compose and re-compose the list. Many builtin operations take advantage of the immutability. By extension, your own programs can also take advantage of this immutability.

answered Nov 19, 2014 at 13:15

Bob Dalgleish

8,2604 gold badges35 silver badges42 bronze badges

2 Comments

Vivek Patil Linksys3966 Over a year ago

Yes but the problem is that I dont want to bring any mutable state in my program. the variable xsa is mutable and anyone can modify its state which is some kind of dangerous indication. So I need to use immutable data structures available from scala.collection.immutable._

Bob Dalgleish Over a year ago

xsa is not a variable ... it's "state" will always be a ListBuffer. The content of the list buffer may change, as the list is built up. However, it is only for the period of time that you are building it up. Once you convert it to a list, it can no longer be changed. The point of immutability is that you encapsulate the mutability.

Collectives™ on Stack Overflow

Immutable DataStructures In Scala

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related