Scala: Variance, Polymorphism And Monad

最近在用Scala写一个用于贝叶斯网络计算的库,用到了很多Scala语言的一些概念。该笔记主要通过举例子的方式通俗地描绘下Scala中型变多态单子的概念。该笔记主要参考自sinisalouc@medium


型变


ScalaString 继承自 AnyRef,直观上我们可以称

String 是一个 AnyRef

但不能说

AnyRef 是一个 String

我们希望程序满足里氏替换原则,从这个角度来看,String 是一个 AnyRef 这个陈述可以看作:所有 AnyRef 能做的事,String 都能做,而 String 能做的事,AnyRef 并不一定能做。

另外,从函数的角度来看,若有一个函数声明时是对类型 AnyRef 进行操作,则直观上认为该方法可以对 String 进行操作,因为 String 是一个 AnyRef。同理若该函数声明时是对 String 进行操作,则直观上无法对 AnyRef 进行操作,因为 AnyRef 不是一个 String。同样的,若一个函数声明时返回的是 AnyRef,则实际返回 String 是合法的,因为 String 是一个 AnyRef,反之则非法。


若有 String 继承自 AnyRef,即 String 是一个 AnyRef,考虑更复杂的情况,此时 List[String] 是不是一个 List[AnyRef] 呢?List[AnyRef] 能做的 List[String] 也能做吗?能对 List[AnyRef] 进行操作的函数,是否也能对 List[String] 进行操作呢?

为了描述以上问题,我们可以拓展以下概念:

  • 子类型:若可以广义地称 S 是一个 T,则称 ST 的子类型,记作 S :< T
  • 协变:若 S :< T,且 L[S] :< L[T],则称 LS,T 上是协变的,简记为 L[+T]
  • 逆变:若 T :< S,且 L[S] :< L[T],则称 LS,T 上是逆变的,简记为 L[-T]
  • 不变:若 T,S 的关系对 L[T],L[S] 的关系无影响,则称 LS,T 上是不变的,也就是Scala中常用的 L[T]

所以,若有 L[+A]S :< T,或 L[-A]L :< S,则此时 L[S] 是一个 L[T]。即 L[T] 能做的事情 L[S] 也能做,能对 L[T] 进行操作的函数也能对 L[S] 进行操作。


那么什么时候让 List[String] 是一个 List[AnyRef],什么时候又让 List[AnyRef] 是一个 List[String] 呢?答案是应确保程序满足子类型特性的逻辑自恰。

那么满足子类型特性的逻辑自恰又是指什么呢?

考虑如下类

class Car  
class SportCar extends Car  
val limo = new Car  
val astonMartin = new SportCar

class Foo[T]{  
  def show(t: T):Unit = println(t)
  def take: T = new T
}
class FooCar extends Foo[Car]  
class FooSportCar extends Foo[SportCar]

val fooCar = new FooCar  
val fooSportCar = new FooSportCar  

若此时 FooT 上是协变的(即 Foo[+T]),即我们称 fooSportCar 是一个 fooCar,那么根据里氏替换原则, fooCar 能做的事(fooCar.show(limo)),fooSportCar 应该也能做,但事实上 fooSportCar.show(limo) 是非法的,因为 fooSportCar.show(t: SportCar) 接受地参数必须是一个 SportCar,而 limo 不是一个 SportCar,此时子类型特性的逻辑不能自恰,有冲突。

若此时 FooT 上逆变的(即 Foo[-T]),即我们称 fooCar 是一个 fooSportCar, 根据里氏替换原则,fooSportCar 能做的事(fooSportCar.show(astonMartin)),fooCar 也能做,事实上,fooCar.show(astonMartin) 也确实能做,因为 astonMartin 是一个 Car,符合 fooCar.show(t: Car) 的参数要求。

所以,对于作为参数值类型的 T,应该确保 Foo 是逆变的,即 Foo[-T],或不变。

同样的思路,考虑 take 方法,此时 T 作为返回值。若有 Foo[-T],则 fooCar 是一个 fooSportCar,此时 fooSportCar.take 返回一个 SportCar,而 fooCar.take 返回一个 Car,由于 Car 不是一个 SportCar,所以和里氏替换原则矛盾。而若有 Foo[+T],此时 fooSportCar 是一个 fooCar,且 fooSportCar.take 的返回值类型 SportCar 是一个 fooCar.take 的返回值类型 Car,满足里氏替换原则,子类型特性的逻辑是自恰的。

所以,对于作为返回值类型的 T,应确保 Foo 是协变的,即 Foo[+T],或不变。


综上,要确保子类型特性的逻辑自恰,应确保:

若有 ST 的子类型,即 S 是一个 T,则必须T 在其所有的方法上,对应参数的类型都是不变或至少存在一个是逆变的,对于返回值的类型都是不变或至少有一个是协变的。

Scala中的单参数函数的特质为例

trait Function1[-S, +T] { def apply(x: S): T }  

该定义下确保了Scala中的单参数函数是存在子类型的,比如

def getSportCarInfo: SportCar => AnyRef  

def getCarInfo: Car => String  

的子类型。


多态


多态包括参数多态子类型多态即时多态,这里主要讨论下即时多态。

以实现一个 appendItems() 函数为例讲解即时多态,该函数接受两个同类型的参数,并对该两参数进行 append 操作,具体如下:

def appendItems[T](a: T, b: T) = a append b  

以仅实现对 IntString 类型为例,下面介绍多种实现思路。


隐式转换

def appendItems[T](a: T, b: T)(implicit: ev: T => Appendable[T]) = a append b  

该声明将告诉编译器,我们许诺编译时你将能找到一个从 TAppendable[T] 的转换法则。考虑到转换成 Appendable[T] 后,实例应具有 append 方法。所以应该有如下特质:

trait Appendable[T] {  
  def append(a: T): T
}

考虑到对于不同的类型,实现 append 的方式也不一样,所以应该有如下类:

class AppendableInt(i: Int) extends Appendable[Int]{  
  override def append(a: Int) = i + a
}
class AppendableString(s: String) extends Appendable[String]{  
  override def append(a: String) = s.concat(a)
}

最后,为了将输入参数 a,b 转换成 Appendable(a),Appendable(b),所以有如下隐式转换:

implicit def toAppendable(i: Int) => new AppendableInt(i)  
implicit def toAppendable(s: String) => new AppendableString(s)  

至此,有

appendItems(2, 3) // 5  
appendItems("2", "3") // "23"  

类型系统

def appendItems[T](a: T, b: T)(implicit ev: Appendable[T]) = ev.append(a, b)  

可以看出,和纯隐式转换不同,类型系统的方法是隐式传入一个 Appendable[T] 的实例 ev,再调用 ev.append(a, b) 实现对 a,bappend 操作。

为了实现这一功能,我们定义如下特质和对应的伴生对象:

trait Appendable[T] {  
  def append(a: T, b: T): A
}

object Appendable {  
  implicit val appendableInt = new Appendable[Int] {
    override def append(a, b) = a + b
  }
  implicit val appendableString = new Appendable[String] {
    override def append(a, b) = a.concat(b)
  }
}

xiehao

Read more posts by this author.