How can I enforce type invariance?

Question

Lists in Scala are covariant (List[A+]). I've found that this is causing me more trouble than anything else, and I'm looking for a way to enforce type invariance on my Lists. The following should give a compilation error:

scala> val l: List[Int] = List(1, 2, 3)
l: List[Int] = List(1, 2, 3)

scala> "string" :: l
res0: List[Any] = List(string, 1, 2, 3)

scala> 1.0 :: l
res1: List[AnyVal] = List(1.0, 1, 2, 3)

Edit: Note that this is a made up example and I would like to know if there is a universal solution that works on all scala Seq, Set and Map, or even any Trait taking a type parameter. If this is not possible and the only option is to give up on the Scala collections for something like scalaz or psp-view, then this is the answer.

Answer 1

You could specify result type:

val rescala> val result: List[Int] = "string" :: l
<console>:8: error: type mismatch;
 found   : String
 required: Int
       val result: List[Int] = "string" :: l
                                        ^

You could also create your own invariant methods like this:

def prepend[T1, T2](t: T1, l: List[T2])(implicit e: T1 =:= T2) = e(t) :: l

prepend(0, l)
// List[Int] = List(0, 1, 2, 3)

scala> prepend("str", l)
<console>:10: error: Cannot prove that String =:= Int.
              prepend("str", l)
                     ^

With value classes you could create invariant wrapper for List without runtime penalty like this:

case class InvariantList[T](l: List[T]) extends AnyVal {
  def ::(t: T) = InvariantList(t :: l)
}

val l = InvariantList(1 :: 2 :: 3 :: Nil)

0 :: l
// InvariantList(List(0, 1, 2, 3))

scala> "str" :: l
<console>:13: error: type mismatch;
 found   : String
 required: Int
              "str" :: l
                    ^

You could also use invariant methods from scalaz for collections concatenation:

import scalaz._, Scalaz._

List(0) |+| List(1, 2, 3)
// List(0, 1, 2, 3)

Vector('a) |+| Vector('b, 'c)
// Vector('a, 'b, 'c)

scala> List("string") |+| List(1, 2, 3)
<console>:14: error: type mismatch;
 found   : Int(1)
 required: String
              List("string") |+| List(1, 2, 3)
                                      ^

Note that (as mentioned by @drexin) there is an invariant list in scalaz: IList.