2023-07-25
TypeScript 里的 ADT
果你是一个学编程的那么几乎每一个语言都会跟你提 "代数数据类型" (Algebraic Data Types, ADT). 网上关于 ADT 的讨论也是经久不衰, 本文准备从实际开发中提炼出我对 ADT 的理解以及个人实践。注意本文讨论的是 Algebraic Data Types 代数数据类型, 而不是 Abstract Data Types 抽象数据类型,两者都叫做 ADT 注意区分
再注意, typescript 开发请务必开严格模式

# ADT 是什么

语言宣称自己支持 ADT 通常是说它的类型系统能提供两种类型:
  1. 1.
    和类型, Sum Types
  2. 2.
    积类型, Product Types

Sum Types 和类型

Sum Types 要求能构造一个新的类型, 比如在 ts 里 enum 是 Sum Types
这里声明的 enum T1 T2 的成员并不是真正的 number, 在 ts 里他们被当做新的类型来处理了, 尽管最后是编译成 number
00// T1 这个类型有一个成员 (取值)
01enum T1 { A, B }
02// T2 这个类型有两个成员 (取值)
03enum T2 { C, D }
04
05// 会报错, 提示不能比较
06if (T1.A === 123) { }
00enum MyBoolean {
01  _true,
02  _false
03}
04
05enum UInt2 {
06  _00,
07  _01,
08  _10,
09  _11
10}
很多司空见惯的类型本质上来说都可以用 Sum Types 去描述的, 左侧 MyBoolean 是 boolean 的一种等价描述,只需要将语言内 if 判断改为判断这个即可认为替代了 “自带的布尔类型”
而下面这个 UInt2 则定义了有 4 种取值分别为 00 01 10 11 的 enum, 而且奇妙的是 enum 最后编译为 number 这里的数字刚好和定义是一样的, 因此可以合理认为这个类型可以实现和描述 Uint2 的各种性质 (需要编写各种函数来单独实现)

Product Types 积类型

Product Types 要求能组合存量的类型构造新类型, 在 ts 里 interface 是一个典型的 Product Types
借助于 Product Types 能将存量的类型取值范围相乘,即右侧 T3 有四种取值,分别对应 T1 T2 两个成员取值范围之乘积
00interface T3 {
01  k1: T1
02  k2: T2
03}
04// { k1: T1.A, K2: T2.C }
05// { k1: T1.A, K2: T2.D }
06// { k1: T1.B, K2: T2.C }
07// { k1: T1.B, K2: T2.D }
Sum Types 具有 “加法” 性质,能构造新类型,Product Types 具有 “乘法” 性质,一样能构造新类型,这些代数性质使其得名 “代数数据类型 ADT”
需要注意, ts 的 enum 并不算完美的和类型, 它有些限制, 比如无法嵌套;同样 interface 也不是完美的积类型, 因为在 ts 里只要长得一样的对象类型都当成是一样的, 这也是网上各种论战的原因, ADT 是好东西, 但是各种语言对其支持程度是不一样的

# 通过 ADT 构建复杂世界的抽象

对于 js/ts 开发来说, 很少需要自己构建一种新的类型, 因为自带的 number / boolean 这些已经能覆盖很多场景了, 反过来积类型用的很多, 比如用 interface 去构造对象描述, 其实就是积类型的一种应用, 下面以一个整数溢出的例子来说明 ADT 怎样用来构造复杂抽象
需要假设未来 js/ts 提供了 Uint8 类型, 它的取值范围是 [0,255] 的整数, 现在有个问题求解过程需要用到 [-255, 255] 的范围, 那么我们可以通过配合 interface 组合 Uint8 来实现描述 [-255,255] 的类型描述 MyInt:
00interface MyInt {
01  sign: boolean
02  value: UInt8
03}
sign 代表正负符号, value 代表 0-255 取值
所以 MyInt 取值范围 2 * 256 - 1 = 511
(两个区间一一对应的话 0 会多算一次, 所以-1)
根据 interface 的积类型性质, MyInt 的取值范围得到了扩大, 使其能满足场景需求,接下来根据场景实现各种不同的方法就能达到抽象目的。
00class MyInt implement MyInt {
01  // 加法
02  add(val: number | MyInt): MyInt {}
03  // 转字符串
04  toString() {}
05  // ... 其他实现
06}

# TS 里 ADT 实践

再举一例,如果需要实现一个左右拖拽 Drag 组件,首先需要定义拖拽 touchStart 的初始位置, 再然后是定义拖拽的位移以及 2d 的位移和拖拽的方向,一个可能的定义是这样的:
00interface DragState {
01  // 描述当前是否在拖拽中 (比如 touchStart 的时候设置为 true)
02  isInDragging: boolean
03  // touchStart 的初始坐标轴位置
04  start?: [number, number]
05  // touchMove 计算两个坐标轴拖拽的位移
06  translation2D?: [number, number]
07  // 拖拽的方向 (string 为 Left Right Down Up 这些)
08  direction2D?: [string, string]
09}
这个定义看上去好像还 OK 能正确描述这些事,实际上它是不靠谱的,比如 isInDragging=true 的时候, start 字段依然可能是可选的, 其他字段也是类似, 这会导致代码里一坨一坨的 if 或者 ? 可选链或者 ! 断言
对于类型抽象,它的取值范围应该刚好对应业务的全部可能性,不能有多不能有少,否则不是一一对应的话很难调试和维护。
ADT 赋予了我们从零构造新类型的能力,基于这个方向重新设计的类型抽象大概长成右边那个样子
按这种思路可以做到一一对应, 进一步完善可以得到下面的完整定义
00type DragState = "不活跃" | {
01  type: "活跃中"
02  // 不是可选的 是确定的
03  start: [number, number]
04  ... 其他字段
05}
00// adt-drag-define.tsx
01
02// 左右拖拽组件定义左和右
03export enum Direction {
04  Center,
05  Left,
06  Right,
07  Up,
08  Down,
09}
10
11// 记录拖拽的 2d 方向
12// 比如如果拖动到左上角则记录为 [.Left, .Up] 代表左上
13export type Direction2D = [Direction, Direction]
14
15// 描述 2d 坐标位移, 可以通过这个位移得到 Direction2D
16export type Translation2D = [number, number];
17
18// 拖拽组件: 不活跃
19export type Inactive = {
20  // 标记为不活跃状态
21  type: 'inactive'
22}
23
24// 拖拽组件: 拖拽中
25export type Dragging = {
26  // 标记为拖拽中状态
27  type: 'dragging',
28  // 记录 onTouchStart 的瞬间坐标
29  start: { x: number, y: number },
30  // 记录 x y 坐标轴的位移
31  translation: Translation2D,
32  // 记录 x y 坐标轴的方向
33  direction: Direction2D,
34}
35
36// 组合状态来描述拖拽组件的全部状态取值
37export type DragState = Inactive | Dragging
可以看到,上面这个类型定义的风格很像 React Redux Action 的类型,这种类型学术上称呼为 tagged-union-types, 简单理解就是带名字的 union-types, 系通过唯一 type 字面量来保证是一个新的类型, 是一种对结构化类型的妥协
通过这种方式可以利用 union-types 实现 Sum Types 构造新类型的特性,关键在于引入一个字面量 type 使得 interface 变得唯一
下面是基于上面的定义实现的拖拽 demo, 可以玩下 (移动端拖拽体验可能差一点, demo 性质懒得弄 passive event 之类的)
上一次拖拽结果:
(0, 0)
(Center, Center)
完整实现如下,已折叠,点击展开
000// what-is-adt-so-called-in-pl/adt-drag.tex
001import React from 'react';
002
003// 前文中的各种定义
004import {
005  DragState, Direction,
006  Direction2D, Translation2D,
007} from './adt-drag-define';
008
009// 移动端解决滚动穿透的问题, 请忽略 (iOS 似乎无效 233)
010import {
011  disableTouchScroll,
012  enableTouchScroll,
013} from '../hooks/disable-touch-scroll';
014
015// 方便同时处理 touch 和 mouse 事件, 这两个长得基本一样
016type DragEvent = React.Touch | React.MouseEvent<HTMLDivElement, MouseEvent>
017
018export function ADTDrag() {
019  const [dragState, setDragState] = React.useState<DragState>({ type: 'inactive' })
020  const [ dx, dy ] = getTranslation2D(dragState);
021  const [ directionX, directionY ] = getDirection2D(dragState)
022  const [lastDragResult, setLastDragReuslt] = React.useState('')
023
024  const onStart = (e: DragEvent) => {
025    setDragState({
026      type: 'dragging',
027      start: { x: e.pageX, y: e.pageY },
028      translation: [0, 0],
029      direction: [Direction.Center, Direction.Center],
030    });
031  }
032
033  // 根据 start 计算位移和 Direction
034  const onMove = (e: DragEvent) => {
035    setDragState(prevState => {
036      if (prevState.type === 'inactive') return prevState;
037
038      // 末减初 得到两个坐标轴的位移
039      const translation: Translation2D = [
040        e.pageX - prevState.start.x,
041        e.pageY - prevState.start.y,
042      ]
043
044      return {
045        ...prevState,
046        translation: translation,
047        direction: [
048          // 根据两个轴位移得到 direction
049          translation[0] > 0 ? Direction.Right : Direction.Left,
050          translation[1] > 0 ? Direction.Down : Direction.Up,
051        ]
052      }
053    });
054  }
055
056  // 设置为不活跃
057  const onEnd = (e?: DragEvent) => {
058    setDragState(prev => {
059      // 只有在 dragging 的时候才记录
060      if (prev.type === 'dragging') {
061        setLastDragReuslt(`${dx}, ${dy}`)
062      }
063      return { type: 'inactive' }
064    })
065  }
066
067  return <>
068    <div
069      style={{
070        position: 'relative', height: '300px',
071        width: '100%', background: '#EEE', 
072        cursor: 'pointer', userSelect: 'none',
073      }}
074      onMouseDown={(e) => onStart(e)}
075      onMouseMove={e => onMove(e)}
076      onMouseUp={e => onEnd(e)}
077      // 兼容 move 到浏览器外部的情况
078      onMouseLeave={e => onEnd(e)}
079      onTouchStart={e => {
080        disableTouchScroll() // 禁用滚动, 解决滚动穿透
081        onStart(e.touches[0])
082      }}
083      onTouchMove={e => {
084        disableTouchScroll() // 禁用滚动, 解决滚动穿透
085        onMove(e.touches[0])
086      }}
087      // 移动端实际没有 e
088      onTouchEnd={e => {
089        enableTouchScroll() // 恢复滚动
090        onEnd(e?.touches?.[0])
091      }}
092    >
093      <div>上一次拖拽结果: {lastDragResult}</div>
094      <div style={{
095        position: 'absolute', textAlign: 'center',
096        background: '#FEE', left: '50%',
097        top: '50%', display: 'inline-block',
098        whiteSpace: 'nowrap',
099        // 根据 dragState 拿到的 dx dy 设置位移
100        transform: `
101          translate(
102            calc(-50% + ${dx}px),
103            calc(-50% + ${dy}px)
104          )
105        `,
106      }}>
107        {/* 位移输出 */}
108        <div>({dx}, {dy})</div>
109        {/* 方向指示 */}
110        <div>({Direction[directionX]}, {Direction[directionY]})</div>
111      </div>
112    </div>
113  </>
114}
115
116/** 获取 state 当前的位移 */
117function getTranslation2D(state: DragState): Translation2D {
118  if (state.type === 'inactive') {
119    return [0, 0]
120  }
121  if (state.type === 'dragging') {
122    return state.translation
123  }
124  return [0, 0]
125}
126
127/** 获取 state 当前的方向 */
128function getDirection2D(state: DragState): Direction2D {
129  if (state.type === 'inactive') {
130    return [Direction.Center, Direction.Center]
131  }
132  if (state.type === 'dragging') {
133    return state.direction
134  }
135  return [Direction.Center, Direction.Center]
136}
看到这里你会喷我, md eczn 这套定义代码量变多了不少,但是实际上这个 DragState 只有两种取值,不活跃和活跃,对应着两个确定的没有带问号的取值
但是对于一开始那个不完备的带好多个问号的 interface, 由于问号较多其取值可能性是 2\*2\*2\*2 十六种, 而真实的业务状态也只有两种, 于是如果你使用那个不完备的定义来写组件的话那么你写代码得处处提防逻辑落入到无效状态中,具体你可以看我这个实现里其实没有各种 if 兜底, 光看代码就能预测软件运行结果了
实际上,主要是 ts 的 ADT tagged-union-types 没有糖, 看看相同的的定义下 swift 的声明和处理是怎样的吧
00enum DragState {
01  // 不活跃 
02  case inactive
03  // 活跃中, 关联两个值 start 和 translation
04  // CGPoint, CGSize 是内置的坐标类型 可以用来描述点和位移
05  case dragging(start: CGPoint, translation: CGSize)
06}
07
08func printState(state: DragState) {
09  switch state {
10    // 因为 state 类型是确定的所以这里可以缩写 .inative
11    case .inative:
12      print("不活跃")
13    // 匹配到拖拽中, 并将关联的两个值存储到变量中 
14    case .dragging(let myStart, let myTranslation)
15      print("拖拽中", myStart, myTranslation)
16  }
17}

# ADT 的重要性

世界上大多数语言都宣称自己支持 ADT, 但从实践来看不同语言里对 ADT 的支持程度并不一样, 这最终会决定写代码的抽象程度和正确性, ADT 支持好的语言最后的代码抽象高, 维护更方便。
反过来则可能需要不断跟底层存储打交道, 比如 C 语言中的 ADT 支持就不算非常完善, 导致很多时候要掺合类型的底层存储,除此之外,语言里各种特性都穿插着 ADT 的思想光辉,下面以几个特性举例

空值和空安全

空安全是典型的和类型设计,在 ts 里可选的值实际上等价于下面这个泛型描述
00type Maybe<T> = null | undefined | T
然后再配合 ? 可选链语法糖来处理形如 Maybe<T> 的类型从而使得大部分可选场景变得简洁易懂

对象

典型的积类型设计, 增加字段来提升对象的取值范围来实现对现实世界的复杂抽象
00interface Person {
01  name: string
02  age: number
03}

enum

和类型设计,能定义出新的类型及其成员
00enum AppColor {
01  Primary,
02  Black,
03  Error,
04}

Union Types

和类型设计,能定义出新的类型及其成员, 但是需要注意 ts 由于对象化类型的原因,这个设计不能算严格的新类型,除非你使用 tagged union types 那样加一个唯一 type 字面量标记
00type Colors = "RED" | "GREEN" | "BLUE"

为什么要喷 Go

我们都知道 go 没有提供 try-catch 其错误处理是通过多值返回的形式搞的, 比如下面这个除法的例子
00func divide(a float64, b float64) (float64, error) {
01  if b == 0 {
02    return 0, errors.New("除 0 错误")
03  }
04  return a / b, nil
05}
06
07func main() {
08  result, err := divide(10, 2)
09  if err != nil {
10    fmt.Println("Error:", err)
11  } else {
12    fmt.Println("Result:", result)
13  }
14}
由于这个经典特性,导致报错的地方要各种判断 err 是不是为空值, 于是有了下面这张经典老梗
除了 try-catch 的问题,最该喷的应该是 go 的这个多值返回是一个积类型,也就是说返回的 (T, Err) 这个多值有四种可能性分别是
  1. 1.
    正常返回: (T, nil)
  2. 2.
    异常返回: (nil, Err)
  3. 3.
    未知返回: (nil, nil)
  4. 4.
    未知返回: (T, Err)
我们实际期望返回的是积类型的两种, 也就是 "null | T", 写过 ts 的你应该懂这段代码的 result 多恶心人吧:
00function divide(a: number, b: number): [number?, Error?] {
01  if (b === 0) return [undefined, new Error("除 0 错误")]
02  return [a / b, undefined]
03}
04const result = divide(123, 0)
05// result 类型是 [number?, Error?] 有四种取值可能性 ...
除法的例子虽然不太可能写出上面 3 和 4 的两种情况,但是软件是复杂的,我们不应该写出业务不可能出现的类型,一旦写出来软件运行就有可能落入未定义的错误状态导致各种恶心人的兜底判断了,这就是为什么要爆喷 go 的原因了

null undefined

js/ts 类似 go 那样值得爆喷的 ADT 设计错误就是 null undefined 两个空值的问题,它会导致类型出现更大的取值范围,导致有时候你甚至要严格区分 undefined 和 null 。。。写过前端的你应该懂的吧, 下面 Obj 实际上相当复杂:
00interface Obj {
01  value?: number | null
02}
03// 1. { value: undefined }
04// 2. { value: null }
05// 3. { value: 3.1415926 }
06// 4. { value: 其他值 } 可能不是数字 ts 无法保证, 有的人喜欢 any
07
08// 有可能 1 和 2 两个对应的状态含义不是一样的... 于是:
09if (obj.value === undeinfed) {}
10else if (obj.value === null) {}
11else if (typeof obj.value === 'number' ) {}
12else {}

# 评估语言的 ADT

能坚持看到这里说明你大概也明白了 ADT 是什么以及重要性了吧,那么如何评估语言对 ADT 支持程度呢? 可以参考不同语言里对二叉树的实现,它又有字段又有递归,还有空树的情况,这种结构非常适合作为评估 ADT 抽象能力的手段,当然也可以看大家如何爆喷各种语言来评估。

Haskell

完美:体现出空树、子树、泛型等特征,赞美 Haskell
00data Tree a =
01    Empty
02  | Node a (Tree a) (Tree a)

Swift

很好:形式上跟 Haskell 像, 体现出空树、子树、泛型等特征, 但是递归的时候要单独给一个 indirect 声明就有点小残念
00enum Tree<T> {
01  case empty
02  indirect case node(T, Tree, Tree)
03}

Kotlin

较好:体现出空树、子树、泛型等特征, 不过值得吐槽的是 kotlin 类型这块感觉不如 Swift
从二叉树这个例子可以看出, 这是 class 声明, 并不是一种抽象的逻辑结构
00sealed class Tree<T> {
01  data class Node<T>(
02    val value: T,
03    val left: Tree<T>?,
04    val right: Tree<T>?
05  ) : Tree<T>()
06}

TypeScript

较好:体现出空树、子树、泛型等特征, 看着虽然好实际上长得像这个的就是二叉树, 这是结构化类型的痛, 不得不品尝, 如果加个 type:"XXX_TREE" 的字段描述就够 sum 了不过有点蠢, 另外也有类似 kotlin 的问题,需要一个类或对象来承载树结构,而不是像 swift haskell 那样是一个逻辑结构
00type Tree<T> =
01  | null
02  | { value: T, left: Tree<T>, right: Tree<T> }

Go

一般 没有空树, 泛型, 使用上大概率很蛋疼的 (新版 go 终于有泛型了)
00type Tree struct {
01    Value int
02    Left  *Tree
03    Right *Tree
04}

Java

一般:没有空树, 泛型, 而且似乎没有办法单独声明类型,必须得跟 class 走
00class TreeNode<T> {
01    T val;
02    TreeNode<T> left;
03    TreeNode<T> right;
04    TreeNode(T val) {
05        this.val = val;
06        this.left = null;
07        this.right = null;
08    }
09}

Brainfuck

糟糕: GPT 才能掌握的语言
00+++++[>++++[>++++<-]<-] # 声明根节点的值为5
01
02>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++. # 在根节点的右节点上存储9
03
04<+++++[-<++++++>]<. # 在根节点的左节点上存储7
05
06>>+++++++++++++++++++++++++++++++++++++++++. # 在右节点的左节点上存储17
07
08<<+++++++++++. # 在左节点的左节点上存储13
09
10>>+. # 在右节点的右节点上存储18
11
12# 上述这段代码描述了这颗树
13      5 
14    /   \ 
15   13    9 
16        / \ 
17       17  18

# TypeSript ADT 最佳实践

下面给一个我认为比较好的一个编码实践, 配合 ESM Module 能获得一个不算差的使用体验: (not bad)
00// option.enum.ts
01import { Enum, EnumTypes } from '..';
02
03enum TypeNone { }
04export type None = { type: typeof TypeNone };
05function None<T>(d: T): None { return { type: TypeNone } };
06function isNone(x: any): x is None { return !!(x && x.type === TypeNone) };
07
08enum TypeSome { }
09export type Some<T> = { type: typeof TypeSome, data: [_: T] };
10function Some<T>(d: T): Some<T> { return { type: TypeSome, data: [d] } };
11export function isSome<T>(x: Option<T>): x is Some<T> { return !!(x && x.type === TypeSome) };
12
13export const Option = {
14  None, isNone, Some, isSome,
15  // 也可以这里补一个 unsafe_unwrap
16}
17
18export type Option<T> = ( // 注意要跟上面同名
19  | None
20  | Some<T>
21);
00// test.ts
01import { Option } from './option.enum';
02function handle(maybe: Option<number>) {
03  if (Option.isSome(maybe)) {
04    const [val] = maybe.data; // maybe is Some<number>
05    return;
06  }
07
08  maybe // ⬅️ is None
09}
等价于:
00enum Option<T> {
01  None,
02  Some<T>
03}
唉,不管怎样用着都很难受,总之没有 ADT 我要死了

# 参考





回到顶部