十年学会函数式编程: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,认识到它和我们之前所理解的类型概念不一样,这个点就和我们的认知体系连接起来了。

comments powered by Disqus