What does the syntax ::[T] =_ means in Scala?

Question

I am trying to understand how is the Listbuffer implemented.

@SerialVersionUID(3419063961353022662L)
final class ListBuffer[A]
      extends AbstractBuffer[A]
         with Buffer[A]
         with GenericTraversableTemplate[A, ListBuffer]
         with BufferLike[A, ListBuffer[A]]
         with ReusableBuilder[A, List[A]]
         with SeqForwarder[A]
         with Serializable
{
  override def companion: GenericCompanion[ListBuffer] = ListBuffer

  import scala.collection.Traversable
  import scala.collection.immutable.ListSerializeEnd

  /** Expected invariants:
   *  If start.isEmpty, last0 == null
   *  If start.nonEmpty, last0 != null
   *  If len == 0, start.isEmpty
   *  If len > 0, start.nonEmpty
   */
  private var start: List[A] = Nil
  private var last0: ::[A] = _
  private var exported: Boolean = false
  private var len = 0
  ...
}

The first question is, I couldn't understand the syntax ::[A] = _ from private var last0. It looks like a type though but what does it mean by ::[A] and why it requires _ on the RHS? It seems that the syntax is used to represent the last element of the List, but how does it work?

The second questions is related to the fact that ListBuffer utilizes Var tail not the Val tail (even it is immutable) to make the addition fast. How can the above += function helps it achieve faster addition???

def += (x: A): this.type = {
  if (exported) copy()
  if (isEmpty) {
    last0 = new :: (x, Nil)
    start = last0
  } else {
    val last1 = last0
    last0 = new :: (x, Nil)
    last1.tl = last0
  }
  len += 1
 this
}

The last question is about how the addition of ListBuffer works. It seems that start points to last0 all the time after the empty ListBuffer is filled with the first element and the start doesn't change until it becomes empty again. And the addition after the first one, changes the tail of the list to the new List created by below code lines.

val last1 = last0 
last0 = new :: (x, Nil)
last1.tl = last0

it looks like the tail of the original list last0 is changed to the new last0 which contains the x, but it seems that this code doesn't really extend the List pointed to by the start. How does it work..? It seems that assigning last0 to the last1.tl appends List(x) to the List pointed to by the start, but I couldn't understand how does it work.

If possible could you explain how the start, last0, last1 will be changed with the input sequence += 1, += 2, += 3, etc?

`::` [is a class](http://www.scala-lang.org/api/current/scala/collection/immutable/$colon$colon.html) and, as such, is a type. — jwvh, Mar 21 '18 at 03:19
@jwvh, Thanks! then what does the "_" mean in RHS of the assignment? — ruach, Mar 21 '18 at 03:21
The RHS `_` is used to initialize a `var` to a default value. The default value is determined according to its type. The default for `Int` is `0`. The default for an instance of `::` is `null`. It''s just one more example of the [many uses of the underscore](https://stackoverflow.com/questions/8000903/what-are-all-the-uses-of-an-underscore-in-scala). — jwvh, Mar 21 '18 at 03:29
@jwvh. Aha! Thanks, then how the += operation works in the ListBuffer? It seems that += operation creates a new List(x) from new ::(x, Nil) and just assign it to the tl of the List pointed to by the start. It seems that last1.tl is just a var List[T] and never append the new element to the List pointed to by the start. — ruach, Mar 21 '18 at 03:33
You have about 5 questions here. If you have 5 questions, please ask 5 questions, not cram then into one. Especially, since most of your questions have already been asked and answered many times on [so] and are thus off-topic for being duplicates. — Jörg W Mittag, Mar 21 '18 at 07:47

user3097405 · Accepted Answer · 2018-03-21T16:00:04.887

The :: can be a method or a class. In the example, it refers to the parameterized class, that adds a new element to the beginning of a List.

scala> var x: ::[Int] = _
x: ::[Int] = null

scala> x = new ::[Int](1, List(2, 3))
x: ::[Int] = List(1, 2, 3)

Although List is immutable, the var x is mutable (ListBuffer is mutable). It starts with a null value and then it is set to a new list.

Finally, the += method appends an element to the list and +=: prepends, and both are constant time operations (unlike with List, that has constant time for prepending and O(n**2) for appending.

If you take a look at the definition of ::, you will see that the tl passed to the constructor is a private var.

final case class ::[B](private var hd: B, private[scala] var tl: List[B]) extends List[B] {
  override def head : B = hd
  override def tail : List[B] = tl
  override def isEmpty: Boolean = false

This means that it can only be modified within the package scala (where it belongs). And ListBuffer belongs to a subpackage scala.collection.mutable and thus can access tl. This is what you see on the else block in the line last1.tl.

So, about appending a new element:

Let’s say x = 42

// start is empty:
last0 = new ::(42, Nil) // List(42)
start = List(42)

Now, we want to add append 43:

// start is not empty
val last1 = List(42) // last1 is the same object as last0
last0 = new ::(43, Nil) // temporarily set last0 to List(43) //
last1.tl = List(43) // as last1 is the same as last0
                    // last0.tl = List(43)
                    // last0 points to the new last element
                    // start holds all elements in the buffer

Chapter 22 of "Programming in Scala" (the first edition is free online) explains how List is constructed and how ListBuffer is used.

I appreciate your help, but how the += works? It seems that assigning List(x) to the tail doesn't expand the original list though... Could you please check the second part of the question and some part of the information I added in the comment? — ruach, Mar 21 '18 at 04:32
I edited my answer. BTW, you have 3 questions in one. If you had separated them, probably more people would be able to answer them separately, instead of you having to wait for someone that could answer all of them. — user3097405, Mar 21 '18 at 05:40
Thanks for the addition and details, but I am curious what happens if one more addition happens. It seems that newly created List(x) is assigned to the last1.tl every time, not concatenated after the previous last1.tl. If it is changed every assignment how does that operation expands the List? — ruach, Mar 21 '18 at 06:00
you can try to follow the same logic from the response. Adding another element would again fall into the `else` block. `last1` will be set to the current `last0`, that is a `List` with 2 elements... I believe I fully answered your questions — user3097405, Mar 21 '18 at 06:07

What does the syntax ::[T] =_ means in Scala?

1 Answers1