Optimized to be empty

Question
1

Sorry for naive question but I think what I am showing below is a bit inconsistent.
We can create a list by doing the following

0 :: 1 :: 2 :: Nil

or equivalently

0 :: 1 :: 2 :: List()

Clear, trivial, but why the following function works

def reverseLeft[T](xs: List[T]) =xs.foldLeft(List[T]()) {(ys, y) => y :: ys}

but not this one

def reverseLeft[T](xs: List[T]) =xs.foldLeft(Nil) {(ys, y) => y :: ys}

In this post I have read that Nil is a specialized object optimized specifically to be empty, and thus very different from List(). This just blows my mind, how do you optimize something to be empty?

2

That is just a limitation of the type inference algorithm which was fixed in Scala 3.

The TL;DR; is that foldLeft is defined like:

def foldLeft[B](z: B)(op: (B, A) => B): B

So the type checker sees that z is Nil which has type Nil.type and thus it fixes the type parameter B to that, which makes everything fail.
When you do: List[T]() that has List[T] as the return type which makes B to be List[T] and everything typechecks.

However, note that since Nil.type <: List[Nothing] <: List[T] (for any type T) both are equivalent and should work the same; and that is basically what the Scala 3 version of the typechecker does, it doesn’t fix B to Nil.type yet, but rather annotates that as a possibility and keeps reading the code before fixing it to List[T] in the end.

BTW; List[T]() has some additional overhead and is not that common, usually you would do: List.empty[T] instead.

Which is defined like this:

object List {
  def empty[T]: List[T] = Nil
}

Well, they are different because List() is a method and Nil is an object, but List() will just return Nil since the code for apply is more or less this:

object List {
  def apply[A](args: A*): List[A] =
    if (args.isEmpty) Nil
    else args.head :: List.apply(args : _*)
}

The real code may be more optimized but the end result is the same, if args is empty it returns Nil

The important difference is just the return type.
For example if you only used List() (without the type parameter) you would get a similar error that with Nil

Is not really an optimization, is just the definition, Nil is the empty List
Remember that List is a very simple structure:

// A List is either an empty list or a non-empty one.
// a non-empty one has a head of type A and a tail of type List[A]
sealed trait List[+A]
final case class Cons[+A](head: A, tail: List[A]) extends List[A]
final case object Nil extends List[Nothing]

That is all.

3 Likes
3

Love your answer, everything makes sense now.

1 Like
4

List() is supposed to be rewritten to Nil, but it’s currently broken:

I’ve gotten into the habit of using empty for collections but not usually for List. I would directly ascribe a type to Nil.

I’ve forgotten what was supposed to be fixed in Scala 3 in the example

scala> def reverseLeft[T](xs: List[T]) =xs.foldLeft(Nil) {(ys, y) => y :: ys}
-- [E007] Type Mismatch Error: ------------------------------------------------------------------------------------------------------------------
1 |def reverseLeft[T](xs: List[T]) =xs.foldLeft(Nil) {(ys, y) => y :: ys}
  |                                                              ^^^^^^^
  |                                                              Found:    List[T]
  |                                                              Required: scala.collection.immutable.Nil.type
  |
  | longer explanation available when compiling with `-explain`
1 error found

how do you optimize something to be empty?

scala> null :: Nil
val res1: List[Null] = List(null)

scala> res1.head
val res2: Null = null

scala> Nil.head
java.util.NoSuchElementException: head of empty list
  at scala.collection.immutable.Nil$.head(List.scala:662)
  ... 32 elided

The empty list is not the list with a null head pointer, for example. Also, head is not represented internally as Option[A]. It is indeed an optimization, albeit that is fundamental to the usual representation of List, that a list can be either empty (in which case it is Nil) or not (in which case it is a ::).

Worth adding that you would optimize a Friday afternoon before a vacation weekend by making it empty.

1 Like
5

I think it would be fair to call it an optimization that there is only ever one empty List at runtime, regardless of what the type parameter is — it’s truly a singleton.

(This already been shown/implied by previous posts, but I wanted to state it explicitly in case the implication wasn’t obvious.)

2 Likes