Smilingleo's Blog

高种泛型 (Generics of a Higher Kind)

January 08, 2014

译者按语：很多翻译中将Kind和Type都翻译为“类型”，但实际上两者还是有不同的，本文中，将Kind翻译为“种类”，取王侯将相宁有种乎之意，是骨子里的东西。而将type译为“类型”。

学习函数式语言如果想真正入门，一个不可避免的话题就是monad/monoid，而这些范畴论中的词汇都异常抽象，难于理解，尤其是对于从java领域转过来的同学，在很多FP的基础东西不了解情况下来研究monad就更加的困难，比如高种泛型。

泛型 我们都知道，就是某种类型的泛化（一般化），就是将某些特殊类型进行抽象，抽出一种一般化的类型T。而高种泛型就是在泛型的基础上再进行一次抽象。

  • First Order Abstraction

    first-order可以理解为”单次抽象“，将特定类型抽象一次，比如类型：T, T是什么？可以是任何具体类型，String，Integer，Date等等，不难发现，这就是Java中的泛型。

  • Higher Order Abstraction

    对应first-order的单次抽象，高阶抽象就是再次抽象，也就是说：在某个东东的抽象上再进行抽象，抽象的抽象。晕了吧！

在继续之前，我们还得熟悉几个概念：

  • 值构造器

    值构造器是一个function / method，接受特定值参数来构造一个特定的值(value)

    值构造器可以有多态：接受不同类型的参数，也可以是抽象abstract的。

  • 类型构造器

    类型构造器是一个类型，接受一个特定类型参数来构造一个特定的类型。

    和值构造器一样，类型构造器也可以有多态，这是高阶类型的关键。

先说这么多概念有什么用呢？我们还是先看一个具体的例子。

例子：Iterable

观察下面代码，我们来玩个找不同的游戏：

trait Iterable[T] {
  def filter(p: T => Boolean): Iterable[T]
  def remove(p: T => Boolean): Iterable[T] = filter(x => !p(x))
}

trait List[T] extends Iterable[T] {
  def filter(p: T => Boolean): List[T]
  override def remove(p: T => Boolean): List[T] = filter(x => !p(x))
}

看到两段代码有什么不同了吗？什么代码重复了？

很容易发现：在List[T]中的两个方法主体结构和Iterable[T]中的几乎完全相同，只是返回类型不同，都期望返回自身类型。如果我们能够将返回类型也复用，那是否就可以完全去除这些重复代码呢？

通过类型构造器多态来去除重复代码

看下面代码：

trait Iterable[T, Container[X]] {
  def filter(p: T => Boolean): Container[T]
  def remove(p: T => Boolean): Container[T] = filter(x => !p(x))
}

trait List[T] extends Iterable[T, List]

这是怎么做到的？很简单，引入了类型构造器多态的概念。上面例子中：Iterable[T, Container[X]]的Iterable是类型构造器，接受两个类型参数，引入多态概念，同样的类型构造器，让其可以接受不同类型的类型参数List。是不是和普通方法多态没什么区别？

public Iterable iterable(T t, Container<X> container) { ... }
public Iterable iterable(T t, List list) { ... }

因为Java的泛型没有类型构造器多态的概念，所以Java泛型无法解决上述重复代码的问题。最多只能将返回类型设为超类Iterable，然后在调用子类实现时将其强制类型转换为具体子类。

有了上面的例子为上下文，我们再来看两个概念：

类型参数、类型成员

  • Type Parameter

    类型参数，比如: List[T]，List具有一个类型参数T。这里的List就是一个类型构造器。List[Int]就是这个类型构造器接受类型参数Int之后构造的具体类型。

  • Type Member

    类型成员，比如：trait List { type T }

    这里T变成了一个trait的成员（抽象的）。在List子类实现中，指定其具体类型，比如：List { type T = Int }。而这里的类型成员也可能参数化，比如：type Container[T]

    注意：这里的List只用来示意，并不是scala中的List实现。

  • Type Parameter Vs. Type Member

    两者很像，只是作用范围和可见性不同:

    • 参数类型只是被参数化的类型的一部分（local，private）。
    • 类型变量就和不同变量一样，被封装在整个body中，可以被继承，显式地引用。
    • 两者可以相互补充。比如类型成员也可以被参数化。

改进Iteratable

对于集合（collection）来说，很多方法，比如：map, flatMap, filter，各有作用，但是其实这些方法都有以下两个共同点：

  1. 遍历一个集合
  2. 产生一个新的集合

仔细想想，是不是所有的这些操作都满足呢？

  • map遍历一个collection，将其中的元素变形为另外类型并产生一个新的集合。
  • flatMap遍历一个集合，将集合中元素转换为一个集合，并最后将“集合的集合”拉平，形成一个新的集合。
  • filter遍历一个集合，判断是否符合过滤条件，并返回所有符合过滤条件的新的集合。

找到共同点，我们就可以将其抽象出来，进而达到复用、减少重复代码的目的。对上面两个共同点，我们可以用Iterator和Builder来进行抽象实现。

// 产生新集合
trait Builder[Container[X], T] {
  def +=(ele: T): Unit
  def finalise(): Container[X]
}
// 遍历（迭代）器
trait Iterator[T] {
  def next(): T
  def hasNext(): Boolean
  def foreach(op: T => Unit): Unit = {
    while(hasNext()) { op(next()) }
  }
}

有了这两点抽象，那我们就可以对Iteratable进行改进：

// 类型参数Container
trait Buildable[Container[X]] {
  // build方法只是返回一个Builder
  def build[T]: Builder[Container[X], T]
}

// Iteratable没有类型参数Container
trait Iteratable[T] {
  // 类型成员Container
  type Container[X] <: Iteratable[X]
  def elements: Iterator[T]
  
  def mapTo[U, C[X]](f: T => U)(b: Buildable[C]): C[U] = {
    val buff = b.build[U]
    val elems = elements
    while(elems.hasNext) {
      buff += f(elems.next)
    }
    buff.finalise
  }
  
  def filterTo[C[X]](f: T => Boolean)(b: Buildable[C]): C[T] = {
    val buff = build[T]
    val elems = elements
    while(elems.hasNext) {
      val elem = elems.next
      if (f(elem)) buff += elem
    }
    buff.finalise
  }
  
  def flatMapTo[U, C[X]](f: T => Iterable[U])(b: Buildable[C]): C[U] = {
    val buff = build[U]
    val elems = elements
    while(elems.hasNext) {
      f(elems.next).elements.foreach(buff += _)
    }
    buff.finalise
  }
  
  def map[U](f: T => U)(b: Buildable[Container]): Container[U] = mapTo[U, Container](f)(b)
  
  def filterTo(f: T => Boolean)(b: Buildable[Container]) : Container[T] =
    filterTo[Container](f)(b)
  
  def flatMap[U](f: T => Iteratable[U])(b: Buildable[Container]): Container[U] = 
    flatMapTo[U, Container](f, b)
    
}

上面的代码中，我们用Buildable和Iterator将前文提到的两个共同点进行抽象，并在Iteratable的实现中，利用这两个抽象：Curried的参数b: Buildable[C]以及def elements: Iterator[T]抽象方法，分别实现了：map, filter, flatMap。

而Iteratable的具体实现，只需要具化上面两个抽象就可以了。比如List的实现：

object ListBuildable extends Buildable[List] {
  def build[T]: Builder[List, T] = new ListBuffer[T] with Builder[List, T]() {
    // `+=` 是scala标准库中ListBuffer的方法
    def finalise(): List[T] = toList
  }
}

class List[T] extends Iteratable[T] {
  type Container[X] = List[X]
  def elements: Iterator[T] = new Iterator {
    ......
  }
}

有了上面的实现，我们就可以利用scala的另外一个机制：implicit来实现根据类型来自动选择匹配的Buildable了。

Scala标准库实现

掌握上面的思想，我们回头再看scala标准库中collection的实现机制，就很容易理解了。scala的collection架构正是基于builders和traversals思想实现的。

package scala.collection.mutable
class Builder[-Elem, +To] {
  def +=(elem: Elem): this.type
  def result(): To
  def clear(): Unit
  def mapResult[NewTo](f: To => NewTo): Builder[Elem, NewTo] = ...
}

可以看出上面的result方法就是：我们例子中的finalise，此外多了clear, mapResult两个方法。

再看看Buildable的实现：

package scala.collection.generic
trait CanBuildFrom[-From, -Elem, +To] {
  // Creates a new builder 
  def apply(from: From): Builder[Elem, To] 
}

在scala中，换了个名字：CanBuildFrom，感觉会更贴切一些（不过从dual的角度就感觉不那么好了）。

上面的apply就是build只是多了一个参数。

再来看Iteratable:

package scala.collection
class TraversableLike[+Elem, +Repr] {
  def newBuilder: Builder[Elem, Repr] // deferred
  def foreach[U](f: Elem => U)        // deferred
          ...
  def filter(p: Elem => Boolean): Repr = {
    val b = newBuilder
    foreach { elem => if (p(elem)) b += elem }
    b.result
  } 
}

类型参数 vs. 类型成员

在上面的例子中，我们同时使用了类型参数和类型成员。

  • Buildable的主要目的是构建某种类型的Container，因此使用类型参数将其显式地暴露给客户端。
  • 对于Iterable，用户更关心的是其中包含的元素类型，而不是容器(Iterable本身就类似个容器了)，所以我们采用类型成员。

关于类型(Type)和种类(Kind)

其实中文“类型”在这里很混淆，将英文中的两个词type、kind都翻译为“类型”了，其实是有差别的，我们这里将type翻译为"类型"，kind翻译为"种类"。

值、特定类型和种类的关系可以从下图中得到解答。

values, types and kinds的关系图

  • 特定类型是对某种特定类型的值进行分类，比如Int是对1，2，3，4等值的分类，1，2，3是值，Int是Type(类型)。
  • 种类是对特定类型的归类，比如对Int, String, List[Int]等类型，我们进行高阶抽象，可以认为这些特定类型都是相同种类的，可以用*来描述。这里*不是用来描述任意值的，而是任意一个特定类型。
  • 种类K可以是* (看下面定义)，也可以是K → K，其中→是种类构造器，用来构造一个用于归纳类型构造器的种类，绕口吧，简单地说就是K → K接受一个种类参数，返回一个新的种类.

Kind的定义

Kind ::= '*(' Type ',' Type ')' | [id '@' ] Kind '→' Kind

*(T, U)种类中T用来描述类型下边界(lower bound)，U为类型上边界(upper bound)。在Scala中，最低边界是Nothing因为它使一切类型的子类，最高边界是Any，它使所有类型的超类。因为我们经常使用upper bound, 所以，我们用*(Nothing, U)，简化为*(U)来描述一个种类，特别地，*(Nothing, Any)可以简化为*。

上文的几个例子：

Scala 类型定义 Kind 定义
Container [ X ] * → *
Pair [ T, U ] * → * → *
Container [ X ] <: Iterable [ X ] X @ * → * (Iterable [ X ] )
C[X <: Ordered [ X ] ] <: Iterable [ X ] X @ * (Ordered [ X ] ) → * (Iterable [ X ] )

有了Kind定义，我们就可以通过其进行Kind推导，比如T的种类是X @ K → K'，如果U的Kind是K，那么很简单的通过替换，我们就可以知道T[U]的Kind是K'。

子种类Subkinding

scala中，我们通过<:或者>:来表述两个类型（type）之间的关系。比如：Int <: Number。

对于种类，我们可以重载<: and >:，用来描述两个种类之间的关系。比如：*(T, U) <: *(T', U')，当且仅当：T' <: T AND U <: U'时上述关系成立。这个相对容易理解，因为T/T'是类型参数，和方法参数一样，是逆变(contravariance)的。

scala编译器正是通过应用这些规则来进行type/kind检查的。比如，scala编译器将对下面代码报错：

class Iterable[Container[X], T]
trait NumericList[T <: Number] extends Iterable[NumericList, T]

你可以点击run按钮试试，看看编译会出现什么结果。

之所以报错，是因为Iterable[NumericList, T]的问题。我们可以应用上面学到的subkinding来分析一下。

NumericList[T <: Number]的种类是：*(Number) → *，很显然，它必须是Iterable的第一个类型参数NumericList的子种类， 也就是：*(Number) → * <: * → *。在→左边的是种类参数，是逆变的(contravariant)，所以这里我们需要：* <: *(Number)，但是这显然是不成立的。所以scala编译器会报错：type T's bounds <: Number are stricter than type X's declared bounds >: Nothing <: Any。

OK then, how to make it work ? 我们需要引入一个新的类型参数：Bound

class Iterable[Container[X <: Bound], T <: Bound, Bound]
trait NumericList[T <: Number] extends Iterable[NumericList, T, Number]

Iterable[Container[X <: Bound], T <: Bound, Bound]的种类是：*(Bound) → * → *(Bound) → * → *

NumericList[T <: Number]的种类是：*(Number) → *，该种类必须是Iterable第一个参数的子种类，也就是：*(Number) → * <: *(Bound) → *，而Bound已经指定为Number，经过替换，就有了：*(Number) → * <: *(Number) → *，左右两边相同，自然是满足要求了。

高种类型

如果你使用scala 2.11.x版本，在REPL中，就可以通过:type来查看一个类型的种类（Kind）了。比如：

scala> :kind -v List
scala.collection.immutable.List's kind is F[+A]
* -(+)-> *
This is a type constructor: a 1st-order-kinded type.

scala> :kind -v Pair[_, _]
scala.Tuple2's kind is F[+A1,+A2]
* -(+)-> * -(+)-> *
This is a type constructor: a 1st-order-kinded type.

可以看到，两者的类型一个是：* → * 另外一个是 * → * → *，而且，两个都是：1st-order-kinded type。那怎么才算是一个higher order kinded type呢？

在上面的图中:Functor[List]是higher order kinded type: (* → *) → *，这个和Pair[_, _]的* → * → *相比，不就多了个括号吗？玄机就再这个括号上：(* → *) → *表示你接受一个一阶类型* → *，然后产生一个最终的类型。类型的类型，所以是高阶类型。

Implicit机制

implicit是scala中一个很强大的东西，其主要出发点是“偷懒”，没错，就是偷懒，让程序员可以偷懒，将本来应该码农干的活交给“编译器”完成。

implicit能帮我们码农的有两个地方：隐式参数和隐式转换。

隐式参数

具体来说，就是你可以将一个方法调用的参数（显式注为implicit）省略掉，编译器会在当前上下文中找能用于补充缺失掉参数的值，如果能找到，就自动填充，找不到就会在编译时报错。比如下面例子：

def foo[T](t: T)(implicit integral: Integral[T]) = { println(integral) }
foo(1)

注意foo(1)中只提供了第一个参数，一个Int值，但是第二个参数被省略了，scala编译器就会查找当前scope中有没有类型为Integral[Int]的implicit值。很幸运，scala.math.Numeric中定义了implicit object IntIsIntegral extends IntIsIntegral with Ordering.IntOrdering，所以编译器会找到IntIsIntegral对象然后自动补充第二个参数。

那我们再试一下foo(1.0)，这个时候，编译器会报错。为什么呢？查查scala.math.Numeric源码，我们就会发现：scala为Double提供了implicit Fractional对象，make sense，double不是整数嘛。同时scala还是提供了一个对象DoubleAsIfIntegral，但并没有标记为implicit，所以编译器找不到。了解了原因，简单做如下改动：

def foo[T](t: T)(implicit integral: Integral[T]) = { println(integral) }
foo(1)
implicit val doubleAsIfIntegral = scala.math.Numeric.DoubleAsIfIntegral
foo(1.0)

现在大家都happy了。

你可以通过implicitly[Integral[Double]]来自行查找是否有符合条件的隐式参数。

隐式转换

implicit的另外一个作用是隐式转换，同样也是帮助码农的。具体讲，就是当你在调用某个方法在某个对象上的时候，如果这个对象的类A并没有定义这个方法，scala的编译器先不会报错，会尝试着在当前scope中查找：

  1. 具有该方法定义的类型 B
  2. 能够将A转换为B的转换器

如果能找到，那么scala将自动进行上述转换，找不到，报错。例如：

"123".map(_.toInt)

"123"是一个java.lang.String类型，String上并没有定义map方法，但是编译器也没有报错，而且顺利执行了。这就是隐式转换：scala编译器会在上下文中找到implicit def augmentString(x: String): StringOps = new StringOps(x)，可以将String转换为有map定义的StringOps。

你可以通过implicitly[String => StringOps]进行自行查找符合条件的转换器。

基于隐式参数和隐式转换，在Scala的类型系统中，有两个语法糖：view bound (CC <% Seq[T]) 和 context bound (T : Integral)。

View Bounds

说实话不知道这个翻译为什么好，在微博上和几位国内scala大牛们探讨过，一些人认为应该直译为：“视界”，我自己倒是觉得应该叫“化界”？因为：

  1. “视界”，可见到的边界，太笼统，含义模糊，“化界”顾名思义，可“转化到的边界”
  2. 化界听上去比较炫，像是玄幻小说中很高深的境界，^_^

You can think of T <% Ordered[T] as saying, “I can use any T, so long as T can be treated as an Ordered[T].” This is different from saying that T is an Ordered[T], which is what an upper bound, T <: Ordered[T], would say.

有时候隐式参数和隐式转换可以同时存在、起作用，比如下面代码：

def getIndex[T, CC](seq: CC, value: T)(implicit converter: CC => Seq[T]) = seq.indexOf(value)

getIndex("abcde", 'c')
getIndex(List(1,3,2,5), 3)

上面代码中CC可以是任何能转换为Seq的类型，所以String和List都可以应用。

首先，converter是一个隐式参数，其次，因为seq对象的类型是CC，其上面并没有定义indexOf方法，所以“隐式转换”介入。

事实上，这个用法非常普遍，所以scala专门为其提供了一个语法糖：view bound CC <% Seq[T]，重写上面代码：

def getIndex[T, CC <% Seq[T]](seq: CC, value: T) = seq.indexOf(value)

运行上面代码，你可以从输出看到scala编译器会将方法重新定义为：getIndex: [T, CC](list: CC, value: T)(implicit evidence$1: CC => Seq[T])Int，和第一种方法一样。

Context Bounds

再看下面一个例子：

def sum[T](list: List[T])(implicit integral: Integral[T]): T = {
    import integral._   // get the implicits in question into scope
    list.foldLeft(integral.zero)(_ + _)
}

这里有一个隐式参数integral类型为Integral[T]，如果方法传入Int，那么scala编译器就会找implicitly[Integral[Int]]，这个我们在隐式参数小节已经说过了。

这里主要关注另外一个问题：list.foldLeft(integral.zero)(_ + _)，其中_的类型应该是T，但是T上面有定义+方法吗？我们先把import integral._去掉，就会发现编译出错：

<console>:8: error: type mismatch;
 found   : T
 required: String
           list.foldLeft(integral.zero)(_ + _)
                                        ^

原来scala编译器尝试着将T转换为String了，这里应该是Predef.any2string起了作用。

加上import integral._，一切工作了。

回头想一下，其实挺有意思的：我们给一个泛型T动态地添加了+方法，但是并不改变T的代码。而这就是context bound的意义。

这个在流行框架Scalaz中应用非常广泛。scala同样为其创建了专门的语法糖：[T : Ordering]。采用语法糖，这个例子可以重写为：

def sum[T : Integral](list: List[T]): T = {
  val integral = implicitly[Integral[T]]
  import integral._
  list.foldLeft(integral.zero)(_ + _)
}

编译器编译之后，会生成一个sum: [T](list: List[T])(implicit evidence$1: Integral[T])T的方法。

这里有点让人confusing的地方是：T: Integral的写法感觉像是说：T是Integral的类型，就像：m: T，可实际上应该认为是：T在Integral的Context中。

结束语

scala的类型系统确实是一个难点，但同时也是要真正掌握scala语言所必须的知识点。很多概念都很晦涩，对于像我们这些凡人，要想掌握没有太好的办法，只能多看、多练、多想。

参考

  1. Adriaan Moors. What is a higher kinded type in scala. StackOverflow. http://stackoverflow.com/questions/6246719/what-is-a-higher-kinded-type-in-scala. 2011
  2. Martin Odersky and Lex Spoon. Architecture of Scala Collection. scala-lang website. http://docs.scala-lang.org/overviews/core/architecture-of-scala-collections.html. 2013
  3. Daniel C. Sobral. Types of Implicits. StackOverflow. http://stackoverflow.com/questions/5598085/where-does-scala-look-for-implicits. 2011
  4. Jed Wesley-Smith. Scala Types Of a Higher Kind. http://blogs.atlassian.com/2013/09/scala-types-of-a-higher-kind/

Prev: Scala函数式异常处理

Next: map/flatMap/for in Action

Blog comments powered by Disqus.
© Wei Liu | 2024