scala.collection.immutable.List[Int] vs custom List constructor List[Int]

Question

I am new to scala. be gentle. I think the problem is that I created a Trait List which conflicts with scala.collection.immutable.List

trait List[T] {
  def isEmpty: Boolean
  def head[T]
  def tail[T]
}

class Cons[T](val head:T, val tail: Option[List[T]]) extends List[T] {
  def isEmpty: Boolean = false
  def head[T] = head
  def tail[T] = tail
}

class Nil[T] extends List[T] {
  def isEmpty: Boolean = true
  def head[T] = throw new IllegalStateException("head")
  def tail[T] = throw new IllegalStateException("tail")
}

// ERROR HERE
// obj with one elem
val one: Cons[Int] = new Cons[Int](1,Option(scala.List[Int]()))

the error is: expected scala.Option[List[Int]], actual scala.Option[scala.collection.immutable.List[Int]]

Thank you.

Answer 1

You have declared tail to be of type Option[List[T]], but you are passing it the result of calling Option(scala.List[Int]()), which is syntactic sugar for Option.apply(scala.List[Int].apply()).

scala.List[Int].apply returns a scala.collection.immutable.List[Int], not a List[Int]. I am not sure why you would expect a built-in Scala method to return an object that it doesn't know anything about. Anyway, the correct solution for this particular error would be to pass an instance of your Nil class instead of trying to pass Scala's Nil.

This has nothing to do with you choosing the name List for your trait. You would have gotten the same error with any other name.

---

Let's take a closer look at your code:

trait List[T] {
  def isEmpty: Boolean
  def head[T]
  def tail[T]
}

You didn't declare a type for head and for tail. This means that the default type that is going to be used is Unit, which means that those methods don't return anything, they only have side-effects. As a result, the following is perfectly legal:

class Cons extends List[Int] {
  override def isEmpty = false
  override def head[Int] = Unit
  override def tail[Int] = Unit
}

In fact, since a return type of Unit means that the return value is just thrown away, even this is legal:

class Cons extends List[Int] {
  override def isEmpty = false
  override def head[Int] = "Hello"
  override def tail[Int] = true
}

So, what you probably want is to declare the return types:

trait List[T] {
  def isEmpty: Boolean
  def head[T]: T
  def tail[T]: T
}

Another problem is that you are declaring a trait with a type parameter T, then declaring a method head with a different type parameter which just happens to have the same name and thus shadows the outer T and declare a method tail with yet another different type parameter.

This is exactly equivalent to

trait List[T] {
  def isEmpty: Boolean
  def head[U]
  def tail[V]
}

There is exactly zero relationship between the three type parameters.

What this means is that for example the following class is perfectly legal:

class Cons extends List[Int] {
  override def isEmpty = false
  override def head[String] = "Hello"
  override def tail[Float] = 1.23
}

And in fact, since you never use T anywhere, you can just leave it out:

trait List {
  def isEmpty: Boolean
  def head[U]
  def tail[V]
}

And likewise for U and V, so what you have actually written is more or less this:

trait List {
  def isEmpty: Boolean
  def head
  def tail
}

But that is not what you intended at all, I would guess!

It seems that you actually expect all the three Ts to be the same. But! That cannot possibly work, since the head is a single element and the tail is a list (or in your case an optional list) … how can a single element and an option of a list possibly have the exact same type? That's impossible!

What you (probably) want instead is something like this:

trait List[T] {
  def isEmpty: Boolean
  def head: T
  def tail: Option[List[T]]
}

Note, however, that the Option doesn't make sense either, since you later actually create a special class to represent an empty list (Nil), you don't need to have an Option here. That is going to be massively confusing because you can have either an existing empty list or a non-existing list but they both mean the same thing. Let's just get rid of the Option:

trait List[T] {
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
}

Lastly, you will notice that we can only ever take elements out of our list, but never put something in. (We can only construct new lists that have additional elements.) This means that our list is actually covariant in its element type, so let's make sure Scala knows this:

trait List[+T] {
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
}

Also, note that you want to make sure that there can only be two subclasses of this: an empty list and a non-empty list. You don't want to have a third kind of list. Therefore, you should make it a sealed trait so that it can only be subclassed within the same compilation unit:

sealed trait List[+T] {
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
}

Now, let's look at the Cons class.

class Cons[T](val head:T, val tail: Option[List[T]]) extends List[T] {
  def isEmpty: Boolean = false
  def head[T] = head
  def tail[T] = tail
}

Again, you have the same shadowing going on here. You don't want three different type parameters, you only want one:

class Cons[+T](val head: T, val tail: Option[List[T]]) extends List[T] {
  def isEmpty = false
  def head = head
  def tail = tail
}

Note also that in your original version, the return types of both head and tail were Unit, so the return values would have just been thrown away.

Again, let's get rid of the Option, since we know that there will always a be a tail, that's what we have Nil for, to represent an empty tail:

class Cons[+T](val head: T, val tail: List[T]) extends List[T] {
  def isEmpty = false
  def head = head
  def tail = tail
}

Also, the val declaration in the constructor already creates a getter method, so we can get rid of those:

class Cons[+T](override val head: T, override val tail: List[T]) extends List[T] {
  override def isEmpty = false
}

Also note that we are not computing anything in isEmpty, so there is no need for it to be a method and re-evaluate false every time; we can simply make it a field:

class Cons[T](override val head: T, override val tail: List[T]) extends List[T] {
  override val isEmpty = false
}

And again, we don't want someone to create another subclass of Cons, because we want to make sure that there are only two. Therefore, we make Cons a final class:

final class Cons[+T](override val head: T, override val tail: List[T]) extends List[T] {
  override val isEmpty = false
}

And, for convenience, let's also make it a case class, so we can use pattern matching on constructor arguments, get a nice automatically defined implementation of toString() and ##, and a companion object with an apply factory method:

final case class Cons[+T](override val head: T, override val tail: List[T]) extends List[T] {
  override val isEmpty = false
}

And lastly, all of that applies for Nil, too, I am not going to go through the same detailed steps again:

final case class Nil[+T]() extends List[T] {
  override val isEmpty = true
  override def head: Nothing = throw new IllegalStateException("head")
  override def tail: Nothing = throw new IllegalStateException("tail")
}

However, note that it does not make sense to have an "empty list of integers", an "empty list of strings" and so on. An empty list is an empty list. Period. There is only one empty list.

So, let's make it an object instead:

case object Nil extends List[Nothing] {
  override val isEmpty = true
  override def head = throw new IllegalStateException("head")
  override def tail = throw new IllegalStateException("tail")
}

This works, because our list is covariant (meaning that a List[X] is a subtype of List[Y] if X is a subtype of Y) and Nothing is a subtype of every type; therefore List[Nothing] is a subtype of every List[T] and thus we can substitute Nil everywhere a List[T] is expected, regardless of what T is.

Finally, we may want to supply a List companion object with an apply factory method for conveniently constructing a List:

object List {
  def apply[T](elements: T*) = elements.foldRight(Nil: List[T])(Cons.apply)
}

In total, our code now looks like this:

sealed trait List[+T] {
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
}

final case class Cons[+T](override val head: T, override val tail: List[T]) extends List[T] {
  override val isEmpty = false
}

case object Nil extends List[Nothing] {
  override val isEmpty = true
  override def head = throw new IllegalStateException("head")
  override def tail = throw new IllegalStateException("tail")
}

object List {
  def apply[T](elements: T*) = elements.foldRight(Nil: List[T])(Cons.apply)
}

val one = Cons(1, Nil)
//=> one: Cons[Int] = Cons(1, Nil)

val three = List(1, 2, 3)
//=> three: List[Int] = Cons(1, Cons(2, Cons(3, Nil)))

val zero = List(1, 2, 3)
//=> zero: List[Nothing] = Nil

// Even pattern matching works:
val (hd Cons tl) = List("a", "b")
//=> hd: String       = "a"
//=> tl: List[String] = Cons("b", Nil)

Answer 2

I think what you want is:

 val one: Cons[Int] = new Cons[Int](1, None)

Or if you want a list of more than one element:

val two: Cons[Int] = new Cons[Int](1, Some(new Cons[Int](2, None)))

Answer 3

OK, I belive (since I overwrite the class List in some way) that I should use my custom "constructors" all the way. So this is the correct line of code:

val one: Cons[Int] = new Cons[Int](1,Option(new Nil[Int]()))