Adding elements to an immutable list in Scala

Question

In Scala the way you add elements to an immutable list as follows:

    val l = 1 :: 2 :: Nil
    l: List[Int] = List(1, 2)

What this means is you first create a Nil (Empty) List, and to that you add 2 and then 1. i.e. These operations are right-associated. So, effectively, it can be re-written in a clearer way, like so:

    val l = (1 :: (2 :: Nil))
    l: List[Int] = List(1, 2)

The question is, if List is supposed to preserve the order of insertion, and if 2 is added first to an empty list and then 1 is added, then why is the answer not l: List[Int] = List(2, 1) ??

user5102379 · Accepted Answer · 2015-02-14 12:11:41Z

1

This is because elements are prepended: first 2 then 1.

From definition of cons method:

  def ::[B >: A] (x: B): List[B] =
    new scala.collection.immutable.::(x, this)

here you can see that each time new instance of case class scala.collection.immutable.:: is created:

case class ::[B](val head: B, var tail: List[B]) extends List[B]

you just use your new element as a head for new list and your whole previous list as its tail.

Also prepend operation for immutable List takes constant time O(1), append is linear O(n) (from Scala docs).

edited Feb 14, 2015 at 12:11

answered Feb 14, 2015 at 9:09

user5102379

1,5129 silver badges9 bronze badges

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

3 Comments

iyerland Over a year ago

Correct. But I think the key point is, to get the correct order we need to do list.reverse ... right?

user5102379 Over a year ago

:: is prepend operation. If you want your list to change the order, then Yes, list.reverse is the best solution.

acjay Over a year ago

This is correct of course, but "prepend" is just a label. We could swap the names of prepend and append, head and last, etc. and we'd still have a conceptually consistent model for what the list does, and then printing the list as List(2, 1) would make perfect sense.

acjay · Accepted Answer · 2015-02-14 08:41:27Z

1

It's just convention. Lists are basically stacks. It's most efficient to access or modify the most-recently added items. You could just as well consider the head of the list to be the final item ordinally, in which case, your suggested notation would be appropriate.

I would speculate that the reason for the convention is that we don't typically put much care into how a list was constructed, but we do often want to consider the first item accessed to be the initial item in the ordering, and so the notation reflects that.

answered Feb 14, 2015 at 8:41

acjay

37.2k6 gold badges60 silver badges104 bronze badges

Collectives™ on Stack Overflow

Adding elements to an immutable list in Scala

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related