# Optimized to be empty

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?

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

1 Like

`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)

val res2: Null = null

... 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

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