Scala List with type parameter

Question

I had a problem coding a function called head, that basically replace the head elements with another for the List invoking it:

List(1,2,3,4).head(4) // List(4,2,3,4)

The code is obviously useless, I was just trying to have fun with Scala. This is the code:

sealed trait List[+A]{
  def tail():List[A]
  def head[A](x:A):List[A]
}

object Nil extends List[Nothing]{
  def tail() = throw new Exception("Nil couldn't has tail")
  def head[A](x:A): List[A] = List(x)
}

case class Cons[+A](x :A, xs: List[A]) extends List[A]{
  def tail():List[A] = xs
  def head[A](a:A): List[A] = Cons(a,xs)
}

object List{
  def apply[A](as:A*):List[A] = {
    if (as.isEmpty) Nil
    else Cons(as.head,apply(as.tail: _*))
  }
}

Cons(1,Cons(2,Nil)) == List(1,2)
Cons(1,Cons(2,Cons(3,Cons(4,Nil)))).tail()
List(1,2,3,4,5,6,7).tail()
List(1,2,3,4).head(4)

It doesn't not compile and I have this error:

Error:(11, 39) type mismatch;
found   : A$A318.this.List[A(in class Cons)]
required: A$A318.this.List[A(in method head)]
 def head[A](a:A): List[A] = Cons(a,xs)

Could you explain why, please?

Regards.

Answer 1

Your problem is that your head method is taking another type A, therefore inside that scope the compiler takes those As as different, i.e., the A defined in the trait is shadowed by the A in head[A].

Also, your head method is taking a covariant element of type A in a contravariant position, so you can't define head as such.

What you can do is defining your head as:

def head[B >: A](x: B): List[B]

Hence, you get:

object S {
    sealed trait List[+A] {
        def tail(): List[A]
        def head[B >: A](x: B): List[B]
    }

    case object Nil extends List[Nothing] {
        def tail() = throw new Exception("Nil doesn't have a tail")
        def head[B >: Nothing](x: B): List[B] = Cons(x, Nil)
    }

    case class Cons[+A](x: A, xs: List[A]) extends List[A] {
      def tail(): List[A] = xs
      def head[B >: A](a: B): List[B] = Cons(a, xs)
    }

    object List {
      def apply[A](as: A*): List[A] = {
        if (as.isEmpty) Nil
        else Cons(as.head, apply(as.tail: _*))
      }
    }
}

Testing this on the REPL:

scala> :load test.scala
Loading test.scala...
defined object S

scala> import S._
import S._

scala> Nil.head(1)
res0: S.List[Int] = Cons(1,Nil)

scala> Cons(1, Nil).head(4)
res1: S.List[Int] = Cons(4,Nil)

Answer 2

You method head does not need a type parameter, since you already have one defined in the class definition and that is exactly the type you want head to receive (if you want head to create a list of the same type of the original).

The error you get is because A is two different types in the context of the method head (the one from the method and the other from the class).

The definition for head should be:

def head(x:A):List[A]