Any drawbacks to Nil[A]?

Language Design
1

There are various ways to create an empty list including

Nil
List.empty
List()

The latter two have the advantage of allowing the user to easily supply an element type

List.empty[A]
List[A]()

which is frequently desirable to prevent type errors related to List[Nothing]. However, Nil doesn’t allow this. You can fake it using

(Nil : List[A])

but that is mildly painful and ugly. I’d rather be able to say

Nil[A]

This is very easy to implement using

case object Nil extends List[Nothing] {
  ...
  def apply[A]: List[A] = Nil
}

Lists already have an apply method (lookup by index), but that method does not conflict with this one.

Does anybody see any drawbacks to adding this method? Other than the (small, I think) drawback of yet one more method in an already overfull API.

For me, the advantage becomes compelling when I’m teaching pattern matching to my students. Pattern matching on lists becomes much more compelling if the patterns look as close as possible to the way you constructed the list. If I want to use Nil in patterns, then I also want to use it when constructing lists, but then (especially with my students) the type error messages involving “Nothing” become a barrier.

If there is interest, I could easily generate a pull request.

4 Likes
2

Looks reasonable at first sight. But a PR would have to target 2.13.x, since different 2.12.x releases must share the same API. The API is changing a lot in 2.13.x anyway, not sure what’s the latest status.

In the time being, you might be able add the method for your students by the enrichment pattern (if you can give them somehow a library to use). Untested:

implicit class wrapNil(n: Nil.type) {
  def apply[A]: List[A] = Nil
}
3

I worry about overloading the meaning of apply to mean both indexing and creation. I feel that adds another kind of confusion (with run-time consequences), possibly worse than Nothing. I agree Nothing is a rough edge, but it’s also a natural consequence of subtyping and variance.

4

Wait, which runtime consequences?

5

I don’t think it’s as big of an issue here because you rarely see a Nil.type. OTOH, it means that Nil is of type Nil.type but Nil[X] is of type List[X]. This could be a source of confusion.

6

Is there an objection to using List.empty[A] when you want to supply an element type?

7

It sounds to me like it will only make teaching harder, since you’ll have
more things to explain.

8

That’s what I do now (use List.empty[A]). But then there’s a pedagogical disconnect between creating an empty list (using List.empty) and pattern matching against an empty list (using Nil).

9

Problem with Nil.type is when you fold over Option, eg:

Some(5).fold(Nil)(number => List(number)) // that won't compile

As for the Nil[A] you can have it slightly different. Instead of Nil[A] it’s easy to make nil[A], just do:

import List.{empty => nil}

Now you can write:

Some(5).fold(nil[Int])(number => List(number)) // will compile

That doesn’t resolve the problem with broken Option.fold, but at least alleviates it slightly.

10

Then use List[A]() / List(). If you want matching factory and extractor you want List.apply / List.unapply (which the above is of course syntactic sugar for).

11

Sure, that satisfies the immediate desire for the two uses to appear similar. I personally dislike invoking the varargs machinery so casually, but I’m willing to accept that that may be a personal bias I just need to get over.

12

In 2.12.4 and 2.13.0-M2, they do conflict in several ways. Given

trait MmmList[+A] {
  def apply(i: Int): A
}

object MmmNil extends MmmList[Nothing] {
  override def apply(i: Int) = ???
  def apply[A]: MmmList[A] = this
}

object Tests {
  def app[A](f: Int => A): A = f(0)

  def supposing[Q](someList: MmmList[Nothing], q: Q)(implicit fromQ: Q => Int) = {
    // doesn't eta-expand with the general form
    val before1 = someList.apply _
    val after1 = MmmNil.apply _
    // ...even if you say which arity you want
    val before2 = someList.apply(_)
    val after2 = MmmNil.apply(_)
    // doesn't eta-expand *in an expected-lambda context*
    val before3 = app(someList.apply)
    val after3 = app(MmmNil.apply)
    // ...even if you say which arity you want. I'm surprised; I thought
    // this would work.
    val before4 = app(someList.apply(_))
    val after4 = app(MmmNil.apply(_))
    // suppresses implicit conversion, which now comes too late
    val before5 = someList(q)
    val after5 = MmmNil(q)
  }
}

All five after variants fail to compile, whereas their before brethren are just fine.

Some improvements to overloads are planned for 2.13 to make collection-strawman practical. As of 2.13.0-M2, however, all five above examples fail in exactly the same way as with 2.12.4. Since these failures are unrelated to the requirements of collection-strawman, there is no motivation to improve matters here.

Whether these conflicts matter is a different question.

This does not work, likely for the same reason adding curried Option#fold as a regular method broke Scalaz’s uncurried form.

13

Thanks for the insight.

14

Automatic eta-expansion is indeed an issue I have noticed while making the compiler and library compile with the new collections. With the new design relying a lot more on overloading, you frequently run into cases where you need to eta-expand explicitly. Adding one more of those cases for List.apply wouldn’t fundamentally change the situation. Unfortunately I don’t have any good ideas how to improve this, other than going back to the 2.12 way of eta-expansion.

Update: I did have an idea in the meantime: https://github.com/scala/scala/pull/6275

15

@tarsa I have vague recollections of this problem more in general; it seems that you often want to call an ADT constructor (here Nil or ::) and upcast to the ADT type (List), just like it happens automatically in other functional languages. I think that’s why at some point Scalaz used to have, e.g., some[A]: Option[A] and none[A]: Option[A].