"There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies." -- C.A.R. Hoare
「型变(Variance)」是一个令人费解的概念，但它却是理解类型系统的重要基石。本文首先讨论型变的基本概念，深入理解型变的基本形态。然后以List, Option为例讲解型变在Scala中的应用；最后通过ScalaHamcrest的实战，加深对此概念的理解和运用。
1. 定义
1.1 术语表
| 英语 | 中文 | 示例 |
|---|---|---|
| Variance | 型变 | Function[-T, +R] |
| Nonvariant | 不变 | Array[A] |
| Covariant | 协变 | Supplier[+A] |
| Contravariant | 逆变 | Consumer[-A] |
| Immutable | 不可变的 | String |
| Mutable | 可变的 | StringBuilder |
其中，Mutable常常意味着Nonvariant，但是Noncovariant与Mutable分别表示两个不同的范畴。
1.2 ****形式化****
「型变(Variance)」拥有三种基本形态：协变(Covariant), 逆变(Contravariant), 不变(Nonconviant)，可以形式化地描述为：
一般地，假设类型
C[T]持有类型参数T；给定两个类型A和B，如果满足A <: B，则C[A]与C[B]之间存在三种关系：
- 如果
C[A] <: C[B]，那么C是协变的(Covariant);- 如果
C[A] :> C[B]，那么C是逆变的(Contravariant);- 否则，
C是不变的(Nonvariant)。
1.3 Scala****表示****
Scala的类型参数使用+标识「协变」，-标识「逆变」，而不带任何标识的表示「不变」(Nonvariable)。
trait C[+A] // C is covariant
trait C[-A] // C is contravariant
trait C[A] // C is nonvariant
2. 准则
事实上，判定一个类型是否拥有型变能力的准则非常简单。
一般地，「不可变的」(Immutable)类型意味着「型变」(Variant)，而「可变的」(Mutable)意味着「不变」(Nonvariant)。
其中，对于不可变的(Immutable)类型
C[T]
- 如果它是一个生产者，其类型参数应该是协变的，即
C[+T]；- 如果它是一个消费者，其类型参数应该是逆变的，即
C[-T]。
2.1 生产者
Supplier是一个生成者，它生产T类型的实例。
trait Supplier[+T] {
def get: T
}
2.2 消费者
Consumer是一个消费者，它消费T类型的实例。
trait Consumer[-T] {
def accept(t: T): Unit
}
2.3 函数
Function1是一个一元函数，它既是一个生产者，又是一个消费者，但它是不可变的(Immutable)。其中，入参类型为-T，返回值类型为+R；对于参数类型，函数是逆变的，而对于返回值类型，函数则是协变的。
trait Function1[-T, +R] {
def apply(t: T): R
}
2.4 数组
与Function1不同，虽然数组类型既是一个生产者，又是一个消费者。但是，它是一个可变的(Mutable)类型，因此它是不变的(Nonvariant)。
final class Array[T](val length: Int) {
def apply(i: Int): T = ???
def update(i: Int, x: T): Unit = ???
}
综上述，可以得到2个简单的结论。
2.5 结论1
对于不可变的(
Immutable)类型：C[-T, +R, S]，
- 逆变(Contravariant)的类型参数
T只可能作为函数的参数；- 协变(Covariant)的类型参数
R只可能作为函数的返回值；- 不变的(Nonvariable)类型参数
S则没有限制，即可以作为函数的参数，也可以作为返回值。
幸运的是，Scala编译器能够完成这个约束的检查。例如，
trait Array[+A] {
def update(a: A): Unit
}
编译器将检测到编译错误。
error: covariant type A occurs in contravariant position in type A of value a
def update(a: A): Unit
^
2.6 结论2
如果
T2 <: T1，且R1 <: R2，那么(T1 => R1) <: (T2 => R2)。
例如，给定两个函数F1, F2。
type F1 = Option[Int] => Some[Int]
type F2 = Some[Int] => Option[Int]
则F1 <: F2成立。
3. 函数式的数据结构
3.1 自制Option
Option是一个递归的数据结构，它要么是Some，要么是None。其中，None表示为空，是递归结束的标识。
使用Scala，可以很直观地完成Option的递归定义。
sealed trait Option[+A]
case class Some[+A](get: A) extends Option[A]
case object None extends Option[Nothing]
因为Option是不可变的(Immutable)，因此Option应该设计为协变的，即Option[+A]。也就是说，对于任意的类型A，Option[Nothing] <: Option[A]，即None <: Option[A]都成立。
3.2 自制List
与Option类似，List也是一个递归的数据结构，它由头部和尾部组成。其中，Nil表示为空，是递归结束的标识。
使用Scala，可以很直观地完成List的递归定义。
sealed trait List[+A]
case class Cons[A](head: A, tail: List[A]) extends List[A]
case object Nil extends List[Nothing]
因为List是不可变的(Immutable)，因此List应该设计为协变的，即List[+A]。也就是说，对于任意的类型A，List[Nothing] <: List[A]，即Nil <: List[A]都成立。
3.2.1 实现cons
可以在List中定义了cons算子，用于在List头部追求元素。
sealed trait List[+A] {
def cons(a: A): List[A] = Cons(a, this)
}
此时，编译器将报告协变类型A出现在逆变的位置上的错误。因此，在遵循「里氏替换」的基本原则，使用「下界(Lower Bound)」对A进行界定，转变为「不变的(Nonvariable)」的类型参数A1。
sealed trait List[+A] {
def cons[A1 :> A](a: A1): List[A1] = Cons(a, this)
}
至此，又可以得到一个重要的结论。
3.2.2 结论3
对于不可变的(Immutable)类型：
C[-T, +R]，
- 当协变类型参数
R出现在函数参数时，使用「下界」R1 >: R进行界定，将其转变为不变的(Nonvariable)类型参数R1；- 当逆变类型参数
T出现在函数返回值时，使用「上界」T1 <: T进行界定，将其转变为不变的(Nonvariable)类型参数T1。
List的cons算子就是通过使用「下界」界定协变类型参数A，将其转变为不变的(Nonvariable)类型参数A1的。而对于「上界」，通过实现ScalaHamcrest的基本功能进行讲述，并完成整个型变理论知识的回顾和应用。
4. 实战ScalaHamcrest
对于任意的类型A，A => Boolean常常称为「谓词」；如果该谓词用于匹配类型A的某个值，也常常称该谓词为「匹配器」。
ScalaHamcrest首先定义一个Matcher，并添加了&&， ||， !的基本操作，用于模拟谓词的基本功能。
class Matcher[A](pred: A => Boolean) extends (A => Boolean) {
self =>
def &&(that: Matcher[A]): Matcher[A] =
new Matcher[A](x => self(x) && that(x))
def ||(that: Matcher[A]): Matcher[A] =
new Matcher[A](x => self(x) || that(x))
def unary_! : Matcher[A] =
new Matcher[A](x => !self(x))
def apply(x: A): Boolean = pred(x)
}
4.1 支持型变
对于函数A => Boolean，类型参数A是逆变的。因此，为了得到支持型变能力的Matcher，应该将类型参数A声明为逆变。
class Matcher[-A](pred: A => Boolean) extends (A => Boolean) {
self =>
// error: contravariant type A occurs in covariant position.
def &&(that: Matcher[A]): Matcher[A] =
new Matcher[A](x => self(x) && that(x))
// error: contravariant type A occurs in covariant position.
def ||(that: Matcher[A]): Matcher[A] =
new Matcher[A](x => self(x) || that(x))
def unary_! : Matcher[A] =
new Matcher[A](x => !self(x))
def apply(x: A): Boolean = pred(x)
}
但是，此时&&, ||将报告逆变类型A出现在协变的位置上。为此，可以使用「上界」对A进行界定，转变为不变的(Nonvariant)类型A1。
对于逆变的类型
Matcher[-A]，当它作为函数函数参数时，其型变能力将置反。因此，定义def &&(that: Matcher[A]): Matcher[A]时，that的类型实际为Matcher[+A]。
class Matcher[-A](pred: A => Boolean) extends (A => Boolean) {
self =>
def &&[A1 <: A](that: Matcher[A1]): Matcher[A1] =
new Matcher[A1](x => self(x) && that(x))
def ||[A1 <: A](that: Matcher[A1]): Matcher[A1] =
new Matcher[A1](x => self(x) || that(x))
def unary_![A1 <: A]: Matcher[A1] =
new Matcher[A1](x => !self(x))
def apply(x: A): Boolean = pred(x)
}
4.2 原子匹配器
基于Matcher，可以定义特定的原子匹配器。例如：
case object Always extends Matcher[Any](_ => true)
case object Never extends Matcher[Any](_ => false)
也可以定义EqualTo的原子匹配器，用于比较对象间的相等性。
class EqualTo[-A](expected: A) extends Matcher[A] (
_ == expected
)
object EqualTo {
def apply[A](expected: A) = new EqualTo(expected)
}
与EqualTo类似，可以定义原子匹配器Same，用于比较对象间的一致性。
class Same[-A <: AnyRef](expected: A) extends Matcher[A] (
expected eq _
)
object Same {
def apply[A <: AnyRef](expected: A) = new Same(expected)
}
其中，A <: AnyRef类型对A进行界定，排除AnyVal的子类误操作Same。类似于类型上界，也可以使用其他的类型界定形式；例如，可以定义InstanceOf，对类型A进行上下文界定，用于匹配某个实例的类型。
class InstanceOf[-T : ClassTag] extends Matcher[Any] (
_ match {
case _: T => true
case _ => false
}
)
object InstanceOf {
def apply[T : ClassTag] = new InstanceOf[T]
}
有时候，基于既有的原子可以很方便地构造出新的原子。
case object IsNil extends EqualTo[AnyRef](null)
case object Empty extends EqualTo("")
4.3 组合匹配器
也可以将各个原子或者组合器进行组装，形成威力更为强大的组合器。
case class AllOf[-A](matchers: Matcher[A]*) extends Matcher[A] (
actual => matchers.forall { _(actual) }
)
case class AnyOf[-A](matchers: Matcher[A]*) extends Matcher[A] (
actual => matchers.exists { _(actual) }
)
特殊地，基于AnyOf/AllOf，可以构造很多特定的匹配器。
object Blank extends Matcher[String] (
"""\s*""".r.pattern.matcher(_).matches
)
object EmptyOrNil extends AnyOf(IsNil, Empty)
object BlankOrNil extends AnyOf(IsNil, Blank)
4.4 修饰匹配器
修饰也是一种特殊的组合行为，用于完成既有功能的增强和补充。
case class Not[-A](matcher: Matcher[A]) extends Matcher[A] (
!matcher(_)
)
case class Is[-A](matcher: Matcher[A]) extends Matcher[A] (
matcher(_)
)
其中，Not, Is是两个普遍的修饰器，可以修饰任意的匹配器；也可以定义针对特定类型的修饰器。例如，可以定义针对字符串操作的原子匹配器和修饰匹配器。
case class Starts(prefix: String) extends Matcher[String] (
_ startsWith prefix
)
case class Ends(suffix: String) extends Matcher[String] (
_ endsWith suffix
)
case class Contains(substr: String) extends Matcher[String] (
_ contains substr
)
如果要忽略大小写，则可以通过定义IgnoringCase，修饰既有的字符串的原子匹配器。
case class IgnoringCase(matcher: Matcher[String]) extends Matcher[String] (
s => matcher(s.toLowerCase)
)
object IgnoringCase {
def equalTo(str: String) = IgnoringCase(EqualTo(str.toLowerCase))
def starts(str: String) = IgnoringCase(Starts(str.toLowerCase))
def ends(str: String) = IgnoringCase(Ends(str.toLowerCase))
def contains(str: String) = IgnoringCase(Contains(str.toLowerCase))
}
4.5 语法糖
有时候，可以通过定义语法糖，提升用户感受。例如，可以使用Not替换Not(EqualTo)，Is替代Is(EqualTo)，不仅减轻用户的负担，而且还能提高表达力。
object Not {
def apply[A](expected: A): Not[A] = Not(EqualTo(expected))
}
object Is {
def apply[A](expected: A): Is[A] = Is(EqualTo(expected))
}
4.6 测试用例
至此，还不知道ScalaHamcrest如何使用呢？可以定义一个实用方法assertThat。
def assertThat[A](actual: A, matcher: Matcher[A]) {
assert(matcher(actual))
}
其中，assert定义于Predef之中。例如存在如下一个测试用例。
assertThat(2, AllOf(Always, InstanceOf[Int], Is(2), EqualTo(2)))
也可以使用&&直接连接多个匹配器形成调用链，替代AllOf匹配器。
assertThat(2, Always && InstanceOf[Int] && Is(2) && EqualTo(2))
5. 未来演进
此处为了演示「型变」的作用，ScalaHamcrest采用了OO与FP相结合的设计手法，在下一章讲解「Scala函数论」时，ScalaHamcrest将采用纯函数式的设计手法实现，敬请关注。
