程序人生

使用 ADT 代数数据类型 进行数据建模

Posted September 1, 2024 ‐ 12 min read

1. 什么是 ADT?

代数数据类型 ADT 是 Haskell 等函数式编程语言中的一个重要概念，通过两种构造方式，即 product type 和 sum type，就可以构造出复杂的 数据结构，并且可以通过 pattern matching 来对这些数据结构进行处理。

  • sum type

      data Bool = True | False
  data Maybe a = Just a | Nothing
  data Either a b = Left a | Right b
  data List a = Nil | Cons a (List a)

    在 Scala 和 Rust 中，sum type 是通过 enum 来实现的。可以这样理解， sum type 的取值空间是所有构造子的并集。

  • product type

          data Pair a b = Pair a b
      data Triple a b c = Triple a b c

    在 Scala 和 Rust 中，product type 是通过 case class 或 struct 来实现的。可以这样理解， product type 的取值空间 是所有构造子的笛卡尔积。

很多的基础类型，例如：boolean, int, float 等都可以视为某种 SUM 类型，但在 scala/rust 等语言中，我们一般将这些类型视为基础类型 （primitive type），基于这些基础类型，通过 SUM / PRODUCT 就可以构造出复杂的数据结构，用于对目标领域的建模。

设计之禅：以静（数据）制动（行为），动静分离

目前更为流行的面向对象编程（OOP）中，使用类（class）来进行数据建模，在 OOP 中更强调如下的方法：

  1. 继承：即通过创建子类的方式。 OOP 中一个类的子类往往是开放的，可以随意的定义新的子类，提供扩展的属性，并改变父类的行为。

    受 Liskov Substitution Principle 的限制, 子类的行为必顿要与父类一致，现实建模中，很少有真正的 is-a 关系，更多的是 has-a 关系。 大部份的继承关系都是错误的设计，因此，现在语言如 rust/go 等都不再提供继承的方式，而是使用组合的方式来实现类似的功能。

  2. 接口定义：一般的，通过 interface 的方式来定义一组行为，子类（或实现者）提供对 interface 的实现。

    OOP 将数据与行为 强行绑定在一起，这样会导致频繁的更新类的定义（扩展方法、变更行为）。一个笑话就是，如果要发送订单的邮件通知，就需要 在订单类中增加一个 sendEmail 方法，如果要发送短信通知，就需要增加一个 sendSMS 方法。假以时日，订单类就会变得臃肿不堪。

    在 DDD 中，有一个 充血模型 和 贫血模型 的概念，充血模型是指领域对象具有丰富的行为，而贫血模型则是指领域对象只有数据，没有行为。 很多的 DDD 理论都倾向于充血模型，并使用 OOP 的方式，将数据与行为耦合在一起。但是，这种方式实际上是教条的，或者在很多方面是 自相矛盾的。 在商业系统中，数据结构（实体、数据库结构）是相对稳定的，但行为则是高度不稳定的，会随着时间、空间的变化而变化。因此，将数据与行为 绑定到一起，实际上是不合理的。

  3. 函数式编程 与 ADT 更倾向于数据的封闭性（而非扩展性），任何对数据模型的修改，都应该维护到一个 ADT 模型中，并通过类型检查的方式来检查现有的 代码是否有正确的覆盖新的类型，通过静态的类型检查，可以避免很多的运行时错误。 当然，这种方式也确实会带来一定的限制：即动态能力会受到限制。 通常情况下，对复杂的系统，我们会更倾向于追求通过静态类型检查即可保证的正确性，而将需要动态性的部分，限制在一个更小的边界内。

设计之禅：穷尽枚举，足够覆盖

在 OOP 中，我们一般会将某一类对象抽象抽象为父类、子类的方式，或者 interface、实现类的方式，然后在使用时，通过多态的方式来进行处理。 而在 ADT 中，我们一般会将某一类对象抽象为一个 enum 类型，然后通过 pattern matching 的方式来进行处理。

2. JSON with ADT

数据结构除了广泛的存在于内存之中，承担着运行过程中的血液和神经的作用，还会被序列化到磁盘、网络中，作为：

  • 持久化存储
  • 网络传输、数据交换
  • 配置文件

从某个角度来看，这些外部的序列化的数据结构承担着更为重要的作用，因为这些数据结构是更加面向人的，需要有良好的可理解性，同时，一般的，它与 运行期的数据结构是有一定的相关性的，某种程度上决定了内部数据结构与处理代码的设计。由外而内，外部决定内部

这些年来，随着 Restful API 的流行，JSON 作为一种轻量级的数据交换格式，已经成为了事实上的标准。很多的系统都使用 JSON 来作为文件存储的格式、 网络传输的格式。相比于 XML，JSON 更加简洁、易读、易写，也更加容易的被程序处理（写一个JSON Parser只需要100-200行代码就足够了，而且性能足够快 ，而XML Parser则可能需要上万行代码），相比于二进制格式，JSON 更加容易的被人类理解，这在网络调试、配置文件等方面有着很大的优势。

JSON 的自由也很容易滥用，一些复杂的系统会随着时间的演化，而导致 JSON 结构的不断的变化，出现很多的质量问题：

  1. 出现大量的冗余字段，或者废弃但遗留的字段。
  2. 历史版本的 字段的结构、类型、语义的变化，导致了很多的兼容性和不一致的问题。

当混乱发展到一定程度，存储文件结构的变化，会变成整个系统沉重的包袱，此时，在代码处理时，需要面对很多的兼容性问题，很多的代码删不得，改不动， 只能不断的通过补丁的方式，叠加分支的方式，来维护这些历史遗留的问题。在这个时候，我们就会发现，JSON 的自由性，实际上是一种负担。

复杂的软件世界，其实并不需要太多的自由，相反，更需要的是保证质量的规则，诸如强类型编程语言，相比于动态语言，就失去了一定的自由，但 可以通过类型体系，更好的保证的代码的正确性。所谓：动态语言一时爽，一直动态一直爽，重构代码火葬场。

同理，rust 语言的 borrow checker 也是一种规则，它限制了程序员的自由，但却可以保证代码的正确性。虽然和编译期的错误交流，对大部份 的初学者是一件痛苦的事情，但是，大部份代码编译通过就可以无错运行，这种感觉是非常美妙的。同理，在code review时，也可以更加专注于 核心逻辑，而无需为一些低级错误而烦恼。

2.1 JSON Schema

类似于XML Schema，JSON Schema 是一种用于描述 JSON 数据结构的规范，它可以描述 JSON 数据结构的类型、结构、约束等信息，本质上就是 JSON 的类型体系。

实际上，JSON schema 相比大部份的编程语言的类型体系，对数据的 constraint 的描述更加丰富，例如：可以描述数据的长度、取值范围、正则表达式等。 我觉得 ADT 中也需要一套 constraint 的描述，这样可以更好的描述数据的约束。 在 design-by-contract 的设计理念中，也需要一种 contract 的描述语言，这些都是目前的语言中缺失的。

通过 JSON schema，我们可以:

  1. 使用 JSON schema 对 JSON 数据结构进行校验。
  2. 在 Visual Code、IntelliJ IDEA 等编辑器中，可以对JSON 编辑来提供更好的提示、补全、校验等功能。
  3. 可以将 Schema 作为元信息，在代码生成、文档生成等方面发挥作用，例如 API 文档等。

2.2 wjson

在我开发的 wjson 中，提供了一种面向 Scala3 ADT 的 JSON 工具包：

  • Bean/JSON 映射支持: 支持 ADT 类型到 JSON 的映射，以及 JSON 到 ADT 类型的映射。
  • JSON Schema generator: 支持自动根据 ADT 类型生成 JSON Schema，便于在前端、IDE等其他工具中对JSON进行数据提示、校验和代码补全等功能
  • 规划的多版本支持功能：可以在后续版本中，增加新的字段，或者废弃旧的字段，支持新版本软件的向下兼容（新版本软件可以读写旧版本文件），和一定程度的 的向上兼容（旧版本软件可以读新版本文件）。 相关的技术文档参考：wjson docs