CODEWITHSUNDEEP
scalaimmutability
VividMan
VividMan

Reputation: 1

How does prepend preserve immutability of a List but append does not?

If we append an element to a list, how is preserving the immutability of the list in Scala? Should not a new list be made? In java if you add a letter to be the first character, then a new String would be made, and strings are immutable in Java. What is the reason for append to be linear time in Scala? Is it to traverse through the whole list and to add at the end or it is linear because we need to create a whole new list since changing the object?

Upvotes: 0

Views: 193

Answers (1)

Mario Galic
Mario Galic

Reputation: 48420

Both prepend and append to a List result in a new List and thus preserve immutability of the List. We can check this like so

val l = List(1)
l.prepended(0)
l.appended(2)
l             // just has List(1) instead of List(0,1,2)

Prepend is constant time because it does not copy the entire list. Instead it just creates new object that holds a reference to the new head and the reference to the previous tail.

def prepended[B >: A](elem: B): List[B] = elem :: this   // new ::(elem, this)

Append is linear time because it does copy the entire list

def appended[B >: A](elem: B): CC[B] = {
  val b = iterableFactory.newBuilder[B]
  ...
  b ++= this  // copy of the entire list happens here
  b += elem
  b.result()
}

Also note retrieving the last element of a List is linear time because List is implemented as a singly linked list, so it does not know the reference to the last element.

Addressing the comment, List can be an efficient structure despite new List being returned as long as you use it correctly in prepend fashion. Sometimes you will have to reverse the list at the end to get the required order, however this is a one-off traversal. Performance should always in the end be measured within particular circumstance by, say, sbt-jmh.

Also be careful not to confuse Array with List. Former is not really a true Scala collection

implicitly[Array[Int] <:< Iterable[Int]] // error

which demonstrates Array is not a subtype of the base of Scala collections. Array is a Java Array and should be used only if measurements absolutely dictate it.

Upvotes: 2

Related Questions