CODEWITHSUNDEEP
scala
ParoTech
ParoTech

Reputation: 347

Scala generic List implementation

While following the coursera Scala course my Odersky, I implemented the below List example:

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

    override def toString() = if(this.isEmpty) "" else  "{" + head + tail + "}"
}

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

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

Then I tried creating diff example and most of them worked except when I wanter to create a sample like List(4,5, List(2,3)).

  val list1 = new Cons(4, new Cons(5, new Nil)) //worked
  val list = new Cons(1, new Cons(2, new Cons(3, new Nil))) //worked

  val mList = new Cons(list1, new Cons(list, new Nil)) //worked

  val nList = new Cons(4, new Cons(list, new Nil)) // DID NOT WORK
  // <console>:11: error: type mismatch;
  // found   : Cons[Cons[Int]]
  // required: List[Any]
  // Note: Cons[Int] <: Any, but trait List is invariant in type T.
  // You may wish to define T as +T instead. (SLS 4.5)
  //        val nList = new Cons(4, new Cons(list, new Nil))

Can someone please help me to understand what I am doing wrong?

Upvotes: 1

Views: 2099

Answers (2)

Shadowlands
Shadowlands

Reputation: 15074

In your constructor for nList, new Cons(list, new Nil) creates a List[List[Int]] (ie. a list of lists of Int). You then combine it with new Cons(4, ..., which would only work for a List[Int], not a List[List[Int]], so the types don't match.

This ought to work:

val nList = new Cons(new Cons(4, Nil), new Cons(list, new Nil)) // List[List[Int]]

A side point: consider making Cons and Nil case classes, then you get a companion object with an apply method for free, allowing you to drop all the news from your code:

val nList = Cons(Cons(4, Nil), Cons(list, Nil))

Upvotes: 3

Andrzej Doyle
Andrzej Doyle

Reputation: 103837

Your problem is with types.

In your first two examples, you have a list of ints (specifically, a Cons[Int]).

However, in the third example, you have a list of lists of ints (i.e. a Cons[Cons[Int]]). This is the case because each element of your list, is itself a list (list1 and list as defined above).

The final example fails, because the arguments passed to the first Cons are 4 (an int) and new Cons(list, new Nil) which is a Cons[Cons[Int]]. There is no type T such that the first argument here is a T and the latter is a List[T], as required by the constructor.

If you wanted a list of ints, there's no need to "wrap" list in another Cons constructor (which makes a single-element list, where that element is itself a list). You can simply use:

val nList = new Cons(4, list)

Upvotes: 2

Related Questions