十年学会函数式编程：Type Class

在上一篇博客中我们聊了ADT，我们知道了ADT也是关于类型的，我们还和面向对象的class做了比较。此时再看到 type class 这样的词语是非常崩溃的，我的天呐到底还有多少和类型相关的专业词汇。Type 我也认识，Class 我也认识，合到一起又是什么鬼？Type Class 确实又是一个难以理解的概念，我觉得难理解和名字起的不好有很大的关系。词汇真的是匮乏，又不能凭空造一个词出来。但是 Type class 又是必须要理解的一个概念，不然的话可能连 cats 的文档都看不懂。

Type class 最早出自 How to make ad-hoc polymorphism less ad hoc 这篇论文。论文是1988年写的，距离现在已经很遥远了。标题很好的解释了 type class 存在的原因。大家看标题可能并不理解，polymorphism 我们都知道是多态，那 ad hoc 是什么意思，ad hoc polymorphism 又是什么？

对于 ad hoc 本身，维基百科说的很明白：“Ad hoc 是一个拉丁文常用短语。这个短语的意思是“特设的、特定目的的（地）、即席的、临时的、将就的、专案的”。这个短语通常用来形容一些特殊的、不能用于其它方面的，为一个特定的问题、任务而专门设定的解决方案。”

ad hoc polymorphism 字面意思也就是“特设多态”，它描述的是一个函数需要为不同类型的参数分别实现逻辑。换一种说法应该马上就明白了，“重载”。比如两个数相乘，3 * 3和3.14 * 3.14都是乘法运算，但整数和小数的算法是不同的。

与特设多态相对应的是参数多态(parametric polymorphism)。比如计算一个列表的长度，这个函数就是参数多态。

def length[T](l: Seq[T]): Int = {
  l match {
    case x::xs => 1 + length(xs)
    case _ => 0
  }
}

通过对比我们发现特设多态需要为每一种类型分别实现算法，而参数多态则不关心参数是什么类型，因此参数多态让我们可以写出更通用的函数，表达能力更强。另外这两种多态只是在特定的场景下的表现形式，两者并不相互对立，一个语言中既能看到特设多态也能看到参数多态。

特设多态的问题

假如我们需要重新实现平方这个函数，同时支持各种数字类型，应该怎么做？最理想的方式应该是写出下面这样一个函数。

def square[T](x: T): T = {
  x * x // error: value * is not a member of type parameter T
}

但是这个函数是编译不了的，因为不是每一种类型都支持乘法。如果按照特设多态的思路，解决方法也很简单，我们可以利用重载，分别为每种类型实现就好了嘛。

def square(x: Int): Int = x * x
def square(x: Double): Double = x * x

现在平方的问题解决了，那如果我需要实现这样一个函数，输入3个参数，返回这3个参数的平方。而且这3个参数既有可能是Int也有可能是Double。理想的写法是下面这样的：

def squares[T1, T2, T3](x: T1, y: T2, z: T3): (T1, T2, T3)

在这个场景下我们还可以用特设多态吗？也不是不可以。如果我们只考虑Int和Double类型，按照上面重载的方法，我们总共需要写8个函数来实现。

def squares(x: Double, y: Double, z: Double) = (x * x, y * y, z * z)
def squares(x: Double, y: Double, z: Int) = (x * x, y * y, z * z)
def squares(x: Double, y: Int, z: Double) = (x * x, y * y, z * z)
def squares(x: Double, y: Int, z: Int) = (x * x, y * y, z * z)
def squares(x: Int, y: Double, z: Double) = (x * x, y * y, z * z)
def squares(x: Int, y: Double, z: Int) = (x * x, y * y, z * z)
def squares(x: Int, y: Int, z: Double) = (x * x, y * y, z * z)
def squares(x: Int, y: Int, z: Int) = (x * x, y * y, z * z)

特设多态的问题很明显了，虽然每个函数的实现都是一样的，我们还是要把每一种参数类型的组合都写出来，非常冗余。如果再增加一种Long类型，这里就需要实现27个函数了。

让特设多态更通用

就上面的场景而言我们无法实现参数多态，那有没有办法让特设多态变的更加通用一点，而不用写大段重复的代码？乘法只有在面对数字的时候才有意义，我们不需要为类似字符串这种类型去实现乘法。数字的类型也是有限的，Int、Double、Long，常用的也就这几种了。我们有没有办法实现一种有限的参数多态呢？只需要写一次squares函数的实现，但是又不需要支持所有的类型。Type class就这样诞生了。看到这里大家应该可以理解上面论文的标题，How to make ad-hoc polymorphism less ad hoc。

Type class 其实更应该叫做 Class of types。Type 是具体的类型，比如上面提到的 Int、Double、Long 这些。Class 则是人为的进行分类。为了解决上面的计算平方的问题，我们可以把这些类型归为一类，这些类型有一个共同的特点，就是他们都支持乘法。如果限制了参数一定属于我们刚刚定义的这个分类，就不需要再重复写8个函数了。

在 Scala 中我们可以这样实现：

package me.jxq.playground

trait Number[T] {
  def multiply(a: T, b: T): T
}

object NumberInstances {
  implicit val intIsNum: Number[Int] = new Number[Int] {
    def multiply(a: Int, b: Int): Int = a * b
  }

  implicit val doubleIsNum: Number[Double] = new Number[Double] {
    def multiply(a: Double, b: Double): Double = a * b
  }
}

object Playground {
  def squares2[T1, T2, T3](
      x: T1,
      y: T2,
      z: T3
  )(numX: Number[T1], numY: Number[T2], numZ: Number[T3]): (T1, T2, T3) = {
    (numX.multiply(x, x), numY.multiply(y, y), numZ.multiply(z, z))
  }
}

import me.jxq.playground.NumberInstances.{intIsNum, doubleIsNum}

class PlaygroundSuite extends AnyFunSuite {
  test("numbers") {
    assert(
      Playground.squares2(3, 4, 5)(intIsNum, intIsNum, intIsNum) == (9, 16, 25)
    )
  }
}

Type class 的定义描述了概念，如上面的 Number，而具体的实现则在 type class instance 中（NumberInstances 这个 object 中的 intIsNum 和 doubleIsNum）。这样一来我们就可以仅实现一次 squares 的核心算法了。上面的Number就是一个 type class。不过以上的写法有点冗余，通过 scala 的隐式转换我们还可以再优化。

object Playground {
  def squares3[T1, T2, T3](
      x: T1,
      y: T2,
      z: T3
  )(implicit numX: Number[T1], numY: Number[T2], numZ: Number[T3]): (T1, T2, T3) = {
    (numX.multiply(x, x), numY.multiply(y, y), numZ.multiply(z, z))
  }
}

class PlaygroundSuite extends AnyFunSuite {
  test("numbers") {
    assert(
      Playground.squares3(3, 4, 5) == (9, 16, 25)
    )
  }
}

上面 sqaures3 通过 implicit 参数将x、y和z的 Number type class 的 instance 自动包含进来，从而实现 multiply 方法。如果再使用 scala 的 context bound，我们还可以写的更简洁一点。

object Playground {
  def squares4[T1: Number, T2: Number, T3: Number](
      x: T1,
      y: T2,
      z: T3
  ): (T1, T2, T3) = {
    (
      implicitly[Number[T1]].multiply(x, x),
      implicitly[Number[T2]].multiply(y, y),
      implicitly[Number[T3]].multiply(z, z)
    )
  }
}

class PlaygroundSuite extends AnyFunSuite {
  test("numbers") {
    assert(
      Playground.squares4(3, 4.0, 5) == (9, 16.0, 25)
    )
  }
}

以上我们自己实现了 Number 这样一个 type class。实际上 scala 内部已经有定义过了（scala.math.Numeric）。

Type class 让我们得以扩充现有类型的功能，而不需要修改原来的代码，也不需要继承原有的类。我们甚至可以针对同一个 class 实现不同的逻辑。既保证了类型安全，又可以灵活的进行扩展。关于 type class 的更多内容建议看一看 Essential Scala 这本书。有些概念如果只看一个文档一本书、一种语言，可能根本不理解，所以不要死磕。Type class 的定义就是一个很好的例子。当时看 Haskell 的 type class 介绍压根就看不懂，始终没能理解 type class 到底有什么用。

搞懂了 Type class 的概念之后，我们再看 cats 的文档 就不会懵逼了，总算可以理解为什么 cats 的文档第一页叫做 Type Classes。cats里面提供的 Semigroup, Functor, Monad 这些可不就是 type class 么，没毛病。文章首图是 tpolecat 整理的 cats 各个 type classes 之间的继承关系，非常的清晰。

下一篇博客我会结合 cats 讲讲函数式编程的实际应用。