Explain the implementation of Scala's immutable List map method

Question

I'm just trying to understand the logic behind the implementation of Scala's List[A] map[B]

Scala 2.12 describes it as such:

final override def map[B](f: A => B): List[B] = {
    if (this eq Nil) Nil else {
      val h = new ::[B](f(head), Nil)
      var t: ::[B] = h
      var rest = tail
      while (rest ne Nil) {
        val nx = new ::(f(rest.head), Nil)
        t.next = nx
        t = nx
        rest = rest.tail
      }
      releaseFence()
      h
    }
  }

I am confused as to how can h be a new list with f applied to each of its elements. h is declared as a val, so how can it be affected by what happens inside the while loop?

does reassigning the value of t retroactively changes the value of h? Wouldn't that make h mutable though?

Answer 1

I'll use as a reference the version of List.scala on latest available commit on the 2.12.x branch of the Scala repository on GitHub, which is slightly different but similar enough.

final override def map[B, That](f: A => B)(implicit bf: CanBuildFrom[List[A], B, That]): That = {
  if (isLikeListReusableCBF(bf)) {
    if (this eq Nil) Nil.asInstanceOf[That] else {
      val h = new ::[B](f(head), Nil)
      var t: ::[B] = h
      var rest = tail
      while (rest ne Nil) {
        val nx = new ::(f(rest.head), Nil)
        t.tl = nx
        t = nx
        rest = rest.tail
      }
      h.asInstanceOf[That]
    }
  }
  else super.map(f)
}

First notice that a val is an immutable reference, not a immutable value. You can mutate an object through an immutable reference if you have access to its mutable state. Notice how t is taken as a mutable reference to h (the value which is ultimately returned) and then a singleton list is associated with t.tl = nx (which corresponds to t.next = nx in your snippet, I believe).

That tl field is the tail of the :: type, kept as mutable state for internal usage only, as you can see here:

/** A non empty list characterized by a head and a tail.
 *  @param head the first element of the list
 *  @param tl   the list containing the remaining elements of this list after the first one.
 *  @tparam B   the type of the list elements.
 *  @author  Martin Odersky
 *  @since   2.8
 */
@SerialVersionUID(509929039250432923L) // value computed by serialver for 2.11.2, annotation added in 2.11.4
final case class ::[B](override val head: B, private[scala] var tl: List[B]) extends List[B] {
  override def tail : List[B] = tl
  override def isEmpty: Boolean = false
}