Scala generic List implementation

Question

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?

Shadowlands · Accepted Answer · 2013-10-02 15:19:01Z

3

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

answered Oct 2, 2013 at 15:19

Shadowlands

15.1k4 gold badges47 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

ParoTech Over a year ago

Yes the option you have given works but it creates {{4},{2,3}} where as I want {4, {2,3}}. And if what you say is correct then how are these interpreted val list1 = new Cons(4, new Cons(5, new Nil)) val list = new Cons(1, new Cons(2, new Cons(3, new Nil)))

Shadowlands Over a year ago

To get something like {4, {2,3}}, which is a list containing an Int and a list, and is therefore of type List[Any], you will need to specifically declare the type you want when calling the inner Cons: new Cons[Any](list, new Nil)

Shadowlands Over a year ago

val list1 = new Cons(4, new Cons(5, new Nil)) results in a List[Int] (in the notation you give, this is "{4,5}"), and val list = new Cons(1, new Cons(2, new Cons(3, new Nil))) also results in a List[Int] ("{1,2,3}")

Andrzej Doyle · Accepted Answer · 2013-10-02 15:18:28Z

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)

Collectives™ on Stack Overflow

Scala generic List implementation

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related