Variant Positions 3

The last few topics all discussed variance in its different forms. The following is a cheat sheet of the where the different variances exist within a class.

See Variant positions 1 for a discussion on one position in a class that is a contravariant position.

The example is:

1. scala> class Output[+A] {def write(a : A) = () /*do write*/ }

In this example A in the method write is an contravariant position. Which means the previous definition is not legal because A is defined as Covariant in the class definition. In a class there are several positions with different variance characteristics. Here's the example from Programming in Scala:

1. abstract class Cat[-T, +U] { 
2.     def meow[W^-](volume: T^-, listener: Cat[U⁺, T^-]^-): Cat[Cat[U⁺, T^-]^-, U⁺]⁺
3. }

If you remove the superscript + and - the above example actually compiles. The + and - indicate if the position is a covariant or contravariant position. Its not critical to memorize the positions (in my opinion). Just look it up as needed. The rule of thumb is that each nested position is inverted (flipped) value of it enclosing position.

That is all I will say about that :)

Variant Positions 2

This is a continuation of post: Variant Positions 1

...

My first attempt at the Verified was to make it a mutable object (my Java tourettes kicking in). But it cannot be covariant and mutable. Look at the code to see why:

1. class Verified[+A <: V,V](assertion : (V) => Boolean, private var value : A){
2.     assert(assertion(value))
3.     
4.     def a = value
5. // update is illegal.  See the example below
6.     def update[ B >: A <: V](a : B) = value = a
7. }
9. def notNull(obj : AnyRef) = obj != null
10. val v = new Verified(notNull, "hi")
12. /*
13. Up to this point everything looks ok but the next line
14. will assign an object to value which is a reference to a String
15. */
16. v update (new Object())

For Verified to be mutable A must be invariant. If you look at the Mutable collections in Scala they are all invariant.

Here is an interesting example of both invariant and covariant type parameters in a class hierarchy:

1. scala> class X[+A](val x :A)
2. defined class X
4. scala> class Y[A](var a: A) extends X[A](a)
5. defined class Y
7. scala> val x: X[Any] = new Y[String]("hi")
8. x: X[Any] = Y@1732a4df
10. scala> x.asInstanceOf[Y[String]].a="ho"

This example is perfectly legal because no matter how X[Any] is used no illegal assignment in Y can occur. The interesting thing is that the object can be used in covariant usecases when only X is required. This is now the collections in Scala can work.

Here is a little example of collections invariance and covariance in action. In List the parameter is covariant but in Buffer it is invariant

1. scala> def printList(l : List[Any]) = print(l mkString " :: ")
2. printList: (l: List[Any])Unit
4. scala> val buffer = Buffer(1,2,3)
5. buffer: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1, 2, 3)
7. scala> printList(buffer)
8. 1 :: 2 :: 3
10. /*
11. ++ is part of Iterable.  Since Iterable is covariant ++ 
12. returns a new buffer it does not modify the existing buffer
13. All mutators are only defined on invariant traits
14. */
15. scala> buffer ++ List(4)
16. res16: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1, 2, 3, 4)
18. scala> res16 eq buffer
19. res17: Boolean = false
21. /*
22. buffer defines += to add an element to the buffer
23. so res27 is the same buffer with an extra element
24. */
25. scala> buffer += 10
26. res27: buffer.type = ArrayBuffer(1, 2, 3, 10)
28. scala> res27 eq buffer
29. res28: Boolean = true

Variant Positions 1

An additional topic on variance to finish up the major points on the topic. The previous two posts:

• In- and Co- variance of type parameters
• Contravariance

contain required information for following this post.

In-, co- and contra- variance are the three types of variance expressible in Scala. I showed how this affects assignments and arguments being pass to methods in the last two topics. This looks at how the different types of variance influences how classes can be defined. In the last post we saw how the compiler complained about a method definition in a covariant class because the compiler recognized that such a definition was inherently dangerous and must be prohibited. The example was:

1. scala> class Output[+A] {def write(a : A) = () /*do write*/ }
2. < console>:5: error: covariant type A occurs in contravariant position in type A of value a
3.        class Output[+A] {def write(a : A) = () /*do write*/ }
4.                                    ^

For an class like Output it does not make sense to have A be covariant so we changed A to be contravariant. However suppose we have a collection type class.

1. class Verified[+A] (assertion : (A) => Boolean, value : A){
2.     assert(assertion(value))
3.     
4.     def a = value
5.     def a_=(a : A) = new Verified(assertion, a)
6. }

The previous definition is not legal because value and a in the parameter of a_= "occur in a contravariant position." What to do? Making A contravariant isn't an option:

1. class Verified[+A <: V,V](assertion : (V) => Boolean, val value : A){
2.     assert(assertion(value))
3. /*
4. this is the key.  Restrict possible types of
5. A Since B is a super (or equal) type of A
6. */
7.     def update[ B >: A <: V](a : B) = new Verified(assertion, a)
8. }
10. // example useage
11. scala> def notNull(obj : AnyRef) = obj != null
12. notNull: (obj: AnyRef)Boolean
14. scala> val v = new Verified(notNull, "hi")
15. v: Verified[java.lang.String,AnyRef] = Verified@307b37df
17. scala> val newV = v update (new Object())
18. newV: Verified[java.lang.Object,AnyRef] = Verified@36f72f09
20. // 3 is not legal because the type parameter 'V' is AnyRef.  Int is a subclass of Any NOT AnyRef
21. scala> val newV = v update (3)           
22. < console>:8: error: inferred type arguments [Any] do not conform to method update's type parameter bounds [B >: java.lang.String <: AnyRef]
23.        val newV = v update (3)
24.                   ^

Contravariance

Continuing on with variance and type parameters, this topic will discuss contravariance. See the post In- and Co- variance of type parameters for the intro material required for this topic.

Covariant parameters allow for an additional dimension of type compatibility:

1. val l : List[Object] = List("this is legal")

Contravariance provides the opposite:

1. // If the type parameter of list was contravariant this would be legal:
2. val l : List[String] = List(new Object())

As covariance is indicated by a '+' before the type contravariance is indicated by a '-'

1. scala> class X[-A]
2. defined class X
4. scala> val l : X[String] = new X[Object]
5. l: X[String] = X@66201d6d

I can almost hear the "cool... but why?". Following the lead in the Programming In Scala book. Consider OutputStream first and a method in a Collection second. (The following code is illegal but consider it)

1. class Output[+A] {def write(a : A) = () /*do write*/ }
3. def writeObject(out : Output[Object]) = out.write("hello")
5. /*
6. Uh oh you this only is for outputting lists not Objects 
7. (certainly not the String that is actually written)
9. Runtime error for sure!
10. */
11. writeObject(new Output[List[String]])

The previous example (if it would compile) would explode because an Output that can only write lists is passed to the method. In the example a String is written to the Output object. The Output[List[String]] cannot handle that.

Fortunately the compiler sees the definition of the class and recognizes this is an error waiting to happen and makes it illegal:

1. scala> class Output[+A] {def write(a : A) = () /*do write*/ }
2. < console>:5: error: covariant type A occurs in contravariant position in type A of value a
3.        class Output[+A] {def write(a : A) = () /*do write*/ }
4.                                    ^

Consider the implications of making A contravariant?

1. // The definition of object is now legal
2. class Output[-A] {def write(a : A) = () /*do write*/ }
4. // this is now a safe method definition since the parameter of Output must be a Object or a super class
5. def writeObject(out : Output[Object]) = out.write("hello")
7. // Now this is illegal as it should be
8. scala> writeObject(new Output[List[String]])
9. < console>:8: error: type mismatch;
10.  found   : Output[List[String]]
11.  required: Output[java.lang.Object]
12.        writeObject(new Output[List[String]])
13.        
14. // this is legal... 
15. scala> writeObject(new Output[Any])

In this example Output[Any] can be passed to the method. This makes sense. If the Output object knows how to write Any oject then it knows how to write an Object; its all good.

In- and Co- variance of type parameters

In Java most parameterized types are considered to be "invariant". What does that mean? Here is an example to explain:

1. /*
2. This is an example of a parameterized class that with an invariant parameter B
3. In both Scala and Java parameters are invariant by default.
4. */
5. scala> class Invariant[B]
6. defined class Invariant
8. scala> var x : Invariant[Object] = new Invariant[Object]
9. x: Invariant[java.lang.Object] = Invariant@2e0c5575
11. /*
12. Note: Invariant[String] cannot be assigned to Invariant[Object]
13.       even though logically it seems like it should be.
14.       This is the effect of invariance.  Covariant parameters do not have
15.       this restriction.
16. */
17. scala> var x : Invariant[Object] = new Invariant[String]
18. < console>:6: error: type mismatch;
19.  found   : Invariant[String]
20.  required: Invariant[java.lang.Object]
21.  var x : Invariant[Object] = new Invariant[String]
22.                              ^
24. scala> class Sub[A] extends Invariant[A]   
25. defined class Sub
27. /*
28. Since Sub is a subclass of Invariant it can be assigned
29. (but not Sub[String])
30. */
31. scala> val x : Invariant[Object] = new Sub[Object]
32. x: Invariant[java.lang.Object] = Sub@26ced1a8

Assignment compatibility has multiple dimensions: the object type and the types of the parameters. Unlike object type the compatibility of the type-parameters can be covariant, contravariant and invariant. Java has invariant parameters and that is demonstrated by the previous example. Covariant parameters allow subclassing. Contravariant parameters need their own topic.

1. // The '+' indicates the parameter is covariant
2. scala> class Covariant[+B]
3. defined class Covariant
5. scala> var x : Covariant[Object] = new Covariant[Object]
6. x: Covariant[java.lang.Object] = Covariant@315cb235
9. // Now this is legal
10. scala> var x : Covariant[Object] = new Covariant[String]
11. x: Covariant[java.lang.Object] = Covariant@26e2e276
13. /*
14. Warning: The following is not legal because 
15.          you cannot supply an invariant parameter 
16.          with a covariant value.
17. */
18. scala> class Sub[+A] extends Invariant[A]
19. < console>:7: error: covariant type A occurs in invariant position in type [+A]Invariant[A] with ScalaObject{def this(): Sub[A]} of class Sub
20.        class Sub[+A] extends Invariant[A]
21.              ^
23. scala> class Sub[+A] extends Covariant[A]
24. defined class Sub
26. scala> class Sub[A] extends Covariant[A] 
27. defined class Sub

Overcoming Type Erasure in Matching 2 (Variance)

A commenter (Brian Howard) on the post Overcoming Type Erasure in Matching 1 made a very good point:

Is there a way to deal with some type arguments being contravariant? Try the following:

class A

class B extends A

val AAFunction = new Def[Function1[A,A]]

((a:A) => a) match {case AAFunction(f) => Some(f(new A)); case _ => None} // this is OK

((a:A) => new B) match {case AAFunction(f) => Some(f(new A)); case _ => None} // this is OK

((b:B) => b) match {case AAFunction(f) => Some(f(new A)); case _ => None} // gives a ClassCastException, since new A is not a B

There is a way to do this, however the information is not captured in the Manifest. A manifest is not designed to do full reflection it is by design very light and has little impact on performance. So to provide the functionality requested by Brian one needs to add that information to the Extractor Definition. Have have a possible solution below.

1. scala> class A
2. defined class A
4. scala> class B extends A
5. defined class B
7. scala> object Variance extends Enumeration {
8.      |     val Co, Contra, No = Value
9.      | }
10. defined module Variance
12. scala> import Variance._
13. import Variance._
15. scala> class Def[C](variance:Variance.Value*)(implicit desired : Manifest[C]) {
16.      |     def unapply[X](c : X)(implicit m : Manifest[X]) : Option[C] = {
17.      |         val typeArgsTriplet = desired.typeArguments.zip(m.typeArguments).
18.      |                                                     zipWithIndex
19.      |         def sameArgs = typeArgsTriplet forall {
20.      |             case ((desired,actual),index) if(getVariance(index) == Contra) => 
21.      |                 desired <:< actual 
22.      |             case ((desired,actual),index) if(getVariance(index) == No) => 
23.      |                 desired == actual 
24.      |             case ((desired,actual),index) => 
25.      |                 desired >:> actual
26.      |         }
27.      |         
28.      |         val isAssignable = desired.erasure.isAssignableFrom(m.erasure) || (desired >:> m)
29.      |         if (isAssignable && sameArgs) Some(c.asInstanceOf[C])
30.      |         else None
31.      |     }
32.      |     def getVariance(i:Int) = if(variance.length > i) variance(i) else No
33.      | }
34. defined class Def
36. scala> val AAFunction = new Def[Function1[A,A]]
37. AAFunction: Def[(A) => A] = Def@64a65760
39. scala> ((a:A) => a) match {case AAFunction(f) => Some(f(new A)); case _ => None}
40. res0: Option[A] = Some(A@1bd4f279)
42. scala> ((a:A) => new B) match {case AAFunction(f) => Some(f(new A)); case _ => None}
43. res1: Option[A] = None
45. scala> ((b:B) => b) match {case AAFunction(f) => Some(f(new A)); case _ => None}
46. res2: Option[A] = None
48. scala> val BAFunction = new Def[Function1[B,A]](Contra,Co)
49. BAFunction: Def[(B) => A] = Def@26114629
51. scala> ((b:A) => b) match {case BAFunction(f) => Some(f(new B)); case _ => None}
52. res3: Option[A] = Some(B@15dcc3ca)