十年学会函数式编程：ADT(Algebraic Data Type)

几乎每一本讲 FP 的书里都会提到 ADT 这个概念，但是好像没有人彻底讲的明白，所以我之前一直不理解。ADT 到底是什么呢？Algebraic 这样的词让人一看就很头疼，写个代码怎么还跟代数产生关系了呢？让我们看看维基百科上的定义：In computer programming, especially functional programming and type theory, an algebraic data type is a kind of composite type, i.e., a type formed by combining other types.

没有什么特殊的，只不过是一种组合类型，由多种其他类型组合而成的类型。Algebraic 是体现在哪里呢？Haskell wiki 是这样描述的：

  1. sum is alternation (A | B, meaning A or B but not both)
  2. product is combination (A B, meaning A and B together)

Algebraic 体现在组合的方式上。把 product 换成 and，sum 换成 or，是不是就容易理解了？product 是 X has an A and a B，sum 则是 X is an A or B。虽然 ADT 看起来很复杂，但其实我们每天都在用，只是没有意识到背后的概念罢了。

比如我们定义一个case class，case class C(a: Boolean, b: Boolean)，C类型同时有两个值a和b，这就是product type。为什么叫product呢？我们来看看C这个case class可以有多少种取值，很显然是 2×2 = 4。正因为取值范围是笛卡尔积(Cartesian Product)，所以才把这种类型叫做 product type。实际上Scala是有 Product 这样一个trait的，而且所有的 case class 都实现了 继承了 Product。

Sum 类型也很常见，比如 Scala 的 Option 类型，它的值可以是 Some(x)，也可以是 None，Either 类型的值可以是 Left(x)，也可以是 Right(y)，他们的共同点是要么是 A 要么是 B，但不能同时是A和B。Sum的名字也一样来源于集合。

在 Scala 里面如何实现一个 Sum Type？非常简单：

sealed trait A
final case class B() extends A
final case class C() extends A

我们还可以定义递归的 ADT，最典型的就是树结构了。

sealed trait Tree[T] {
  val value: T
}
final case class Leaf[T](value: T) extends Tree[T]
final case class Node[T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T]

有了 ADT 我们就可以实现模式匹配，进而对数据进行解构(desctructure)。这是一种非常强大的语法，比如需要计算Tree的高度，可以这样实现：

sealed trait Tree[T] {
  val value: T

  def height(): Int = {
    this match {
      case Leaf(_) => 1
      case Node(_, left, right) => max(left.height, right.height) + 1
    }
  }
}

大多数关于 ADT 的文章，基本讲到这里就停止了，但这些还不足以理解 ADT，就好比只看到单个点，还是无法理解全局，只有把所有的点连起来才会领会。

再来回顾 ADT 的定义，一种由其他类型组合而成的类型，有点熟悉对吧？面向对象中的类不也是由其他类型组成的么，那类为什么不是 ADT 呢，他们有什么差异？我们来尝试着比较一下：

  1. 面向对象中的类可以拥有其他类型的成员变量，这也是组合了其他的类型，但这种组合方式只能实现 product type，无法实现 sum type。
  2. 类的数据是可变的，ADT 的数据都不可变。
  3. 类的实现包含了它所支持的操作，但 ADT 只有数据没有操作。

看起来我们确实能找到很多差异，而且 ADT 好像更高级。但是再想一下，我们真的不能用类来实现 ADT 吗？既然已经实现了 product type，那只要再实现 sum type 就好了。现在问题就变成了：我们能用类来实现 sum type 吗？当然可以了，C++的std::variant就可以表达一个变量要么是 A 要么是 B。C++ 虽然没有模式匹配，但是可以通过 visitor 模式来实现类似的功能。

struct SampleVisitor {
  void operator()(int i) const { std::cout << "int: " << i << "\n"; }
  void operator()(float f) const { std::cout << "float: " << f << "\n"; }
  void operator()(const std::string& s) const {
    std::cout << "string: " << s << "\n";
  }
};

int main() {
  std::variant<int, float, std::string> intFloatString;
  std::visit(SampleVisitor{}, intFloatString);
}

ADT 和类真的具有可比性吗？汽车和船都是交通工具，都有发动机，但是比较汽车和船之间的差异没有意义。虽然类和ADT看起来都是“组合类型”，但并不具备很强的可比性，类是一种具体的语法结构，ADT则更像一种规范和描述。当面对新事物时，我们往往会拿它已经了解的东西进行比较，进而理解新事物。如果在我们现有的知识体系内找不到可以和它类比的东西，那它就是超出认知范围的，这就是ADT难以理解的原因。不过，经过这样一番思维上的辩证之后，我们算是尝试从另一个角度来看ADT，认识到它和我们之前所理解的类型概念不一样，这个点就和我们的认知体系连接起来了。