用 java 實現代數數據類型

一、代數數據類型

Ⅰ、基本定義

根據維基百科 Algebraic data type 的定義，代數數據類型其他類型進行組合的一種複雜的數據結構，根據組合的方式分爲積類型和和類型。

積類型（Product Type）可以理解为结构体类型，該類型可以由一到多个類型组成。比如，用積類型表示一个人的信息，包括姓名、年龄、地址等多个属性。

和类型（Sum Type）可以理解为联合类型，表示一个类型可以是多个类型之一。比如，用和類型表達訂單狀態，值可能是“已支付”、“已发货”、“已取消”等之一。

Ⅱ、理解積與和

對於一個類型 T，其可能的取值集合為 S，對應的長度為 |S|。比如對於下面的枚舉 Nums 類型，其 S = {ONE, TWO, THREE}，|S| = 3。

enum Nums {
    ONE, TWO, THREE
}

假設有類型 T1，T2 對應的取值集合為 S1，S2。

那麽可以定義和類型為 T_SUM = T1 || T2，所形成的集合為 S_SUM = {x | x ∈ S1 or x ∈ S2}, |S_SUM| = |S1| + |S2|。可見和類型是對類型做邏輯或運算，形成的結果集合的長度為運算分量的集合長度之和。

對於積類型，是運算類型閒做笛卡爾積，長度為對應運算分量集合長度的乘積。定義如下：T_PRO = T1 x T2, 所形成的集合為 S_PRO = {(x, y) | x ∈ S1 && y ∈ S2}, |S_PRO| = |S1| * |S2|。

二、實現積類型

java 原生支持積類型，直接使用 class 表示即可。如下代碼所示，Point 為一個積類型，對應的 x，y 分量，該 Point 的取值爲 (x, y) 的所有可能性。

class Point {
    int x;
    int y;
}

三、實現和類型

之前 Java 對和類型的支持並不好，一個相近的是枚舉類型，如下：

enum State {
    ONE("one"), TWO("two"), THREE("three")

    String msg;
    State(String s) {
        msg = s;
    }
}

缺點是無法為每個分量單獨定義特定的數據類型，每個分量都是相同的積類型。可考慮通過接口或抽象類的方式分別為每種類型定義一個類。Option 是一般上需要實現為和類型的類型，包含兩個類，其中 None 代表數據不存在，Some 代表數據存在，任何一個變量必然屬於這兩種情況之一。因此一下用 Option 做例子，來看看具體的實現。

interface MyOptionI<T> {}
class MyOptionINone<T> implements MyOptionI<T> {}
class MyOptionISome<T> implements MyOptionI<T> {
	public T value;
	public MyOptionISome(T v) {
		this.value = v;
	}
}

abstract class MyOption<T> {}
class MyOptionNone<T> extends MyOption<T> {}
class MyOptionSome<T> extends MyOption<T> {
	public T value;
	public MyOptionSome(T v) {
		value = v;
	}
}

這樣的代碼在使用的時候就需要通過 instance 進行判斷，這樣沒有語法支持使用起來比較麻煩。而且由於代碼可能發生變動，產生新的類繼承了抽象類或實現接口，if 無法保證判斷了所有情況。

MyOptionINone<Integer> opt = new MyOptionINone<Integer>(Integer.valueOf(100));
if (opt instanceof MyOptionINone) {
    System.out.println("opc is null");
} else if (opt instanceof MyOptionISome) {
    MyOptionISome<T> opci = (MyOptionISome<T>)opt;
    System.out.println("opc data: " + opci.value);
}

在後續的 Java 改進中增加了 record，封閉類及 switch 模式匹配，這個問題得到一定緩解，具體實現代碼如下：

sealed interface MyOptionR<T> {
	T orElse(T other);
	public record None<T>() implements MyOptionR<T> {
		public T orElse(T other) {
			return other;
		}
	}
	public record Some<T>(T value) implements MyOptionR<T> {
		public Some {
			if (value == null) {
				throw new NullPointerException();
			}
		}

		public T orElse(T other) {
			return value;
		}
	}
}

上面新定義了一個 MyOptionR 接口，其兩個實現的 record 為 None 和 Some，均實現了對應接口。接下來是使用 switch 來判斷變量類型：

MyOptionR<String> opc = new MyOptionR.Some<String>("foo");
switch (opc) {
    case MyOptionR.None<String>() -> System.out.println("None");
    case MyOptionR.Some<String>(String value) -> System.out.println(value);
}

此外，如果想爲類型增加行爲方法，則需要在接口，每個實現的 record 裏面增加對應的方法，如上面定義的 orElse 方法，為每個類型實現一個。相比於原版來説，將 if 分支拆開放在每個類中，但是代碼量相比是增加了的。如果只是單純存儲數據則會比較方便，比如定義二叉樹的結點，其中不添加任何其他方法。下面定義了二叉樹節點及求深度的方法：

sealed interface TreeNode {
	public record EmptyNode() implements TreeNode {}
	public record Node(int value, TreeNode left, TreeNode right) implements TreeNode {}
}

int depth(TreeNode root) {
    switch (root) {
        case TreeNode.EmptyNode() -> {
            return 0;
        }
        case TreeNode.Node(int value, TreeNode left, TreeNode right) -> {
            return Math.max(depth(left), depth(right)) + 1;
        }
    }
}

四、總結

由於 Java 最近發展很快，引入了一堆新特性，record 的引入及相關配套設施為代數數據類型的實現簡化了一些步驟，有利於通過其解決一些問題。