在 Java 中实现完整的 Haskell 风格类型类解析

# 在 Java 中实现完整的 Haskell 风格类型类解析 原文来源: https://garciat.com/posts/java-type-classes/ [返回首页](https://garciat.com/) 2025年12月6日 · 预计阅读79分钟 · 标签: Haskell, Java ## 目录 1. [TL;DR](#tldr) 2. [引言: 什么是类型类?](#intro-what-are-type-classes) 3. [目标: 以编程方式实例化见证](#goal-programmatically-instantiating-witnesses) 4. [补充: Java 泛型与类型擦除](#aside-java-generics-and-type-erasure) 5. [补充: 捕获静态类型](#aside-capturing-static-types) 6. [补充: 理解 `java.lang.reflect.Type` 的层次结构](#aside-understanding-javalangreflecttypes-hierarchy) 7. [子目标: 将 `java.lang.reflect.Type` 解析为 AST](#subgoal-parsing-javalangreflecttype-into-an-ast) 8. [回顾](#recap) 9. [子目标: 见证解析](#subgoal-witness-resolution) 10. [补充: 类型合一](#aside-type-unification) 1. [代码清单: `ParsedType` 的类型合一算法](#listing-type-unification-algorithm-for-parsedtype) 2. [附加: 针对静态方法的类型表示](#extra-a-type-representation-for-static-methods) 11. [子目标: 见证解析，第二部分](#subgoal-witness-resolution-part-2) 12. [回顾](#recap-1) 13. [子目标: 见证解析实现](#subgoal-witness-resolution-implementation) 14. [示例: 一阶类型类与实例](#examples-first-order-type-classes--instances) 1. [类型类: Show](#type-class-show) 2. [类型类: Monoid 与 Num](#type-class-monoid--num) 3. [类型类: PrintAll](#type-class-printall) 4. [类型类: 类型相等性!](#type-class-type-equality) 15. [目标: 高阶类型类](#goal-higher-order-type-classes) 16. [补充: 什么是 Kind?](#aside-what-is-a-kind) 17. [补充: Java 中的高阶类型](#aside-higher-kinded-types-in-java) 18. [子目标: 扩展 `ParsedType` 以支持 HKT](#subgoal-extending-parsedtype-to-support-hkts) 19. [补充: 对 Java 内嵌 HKT 进行 Kind 检查](#aside-kind-checking-java-embedded-hkts) 20. [示例: 高阶类型类](#examples-higher-kinded-type-clases) 1. [类型类: Traversable](#type-class-traversable) 2. [类型类: Functor、Applicative、Monad](#type-class-functor-applicative-monad) 21. [回顾](#recap-2) 22. [结论](#conclusion) 1. [未来工作](#future-work) 2. [相关工作](#related-work) 23. [附录: 上下文实例](#annex-context-instances) 24. [附录: 重叠实例](#annex-overlapping-instances) ## TL;DR 本文探讨了 Java 类型系统的极限——通过纯 Java 构建一个小型的 Haskell 风格类型类实例解析引擎。仅利用反射、泛型类型元数据和一个小型的一阶合一器（unifier），我们就能自动解析类型类实例（包括高阶类型类实例），支持重叠实例，并为任意嵌套的泛型类型推导出见证。本文并非面向生产环境的方案，而是一个实验，它揭示了 Java 在运行时保留了多少结构信息——以及在不做语言改造的前提下，它能多么令人惊讶地接近类型级编程。 你也可以直接跳转到 [这个 gist 中的完整实现](https://gist.github.com/Garciat/204226a528018fa7d10abb93fa51c4ca)。 **更新:** 我已将该项目发布为 GitHub 仓库: [github.com/garciat/java-type-classes](https://github.com/garciat/java-type-classes)。 ## 引言: 什么是类型类? 请看如下代码: ```java interface Equatable<T> { boolean eq(T other); } record Point(int x, int y) implements Equatable<Point> { @Override public boolean eq(Point other) { return x == other.x() && y == other.y(); } } ``` 这是一个相当简单的 OOP 风格泛型接口。但是: ```java record Dup<A>(A fst, A snd) implements Equatable<Dup<A>> { @Override public boolean eq(Dup<A> other) { return fst.eq(other.fst()) && snd.eq(other.snd()); // 错误: 类型 A 中没有 eq() 方法! } } ``` 在不知道 `A extends Equatable<A>` 这一前提的情况下，我们无法为 `Dup` 实现 `eq()`。那么我们来试试加上这个约束: ```java record Dup<A extends Equatable<A>>(A fst, A snd) implements Equatable<Dup<A>> { @Override public boolean eq(Dup<A> other) { return fst.eq(other.fst()) && snd.eq(other.snd()); // OK } } ``` 现在代码可以编译了。然而，`Dup` 现在只能与继承自 `Equatable` 的类型配合使用。`Dup` 的适用范围变窄了。我们也可以在运行时对每个对象做 `instanceof Equatable` 检查，但这与泛型配合得并不好，而且可能在运行时失败。理想情况下，应该有一种方式来表达: **`Dup` 实现 `Equatable<Dup<A>>` 当且仅当 `A` 实现 `Equatable<A>`。** > 另外，仔细想想，一个类型 `A` 的相等性定义居然依赖于对象实例，这本身就有点奇怪。也就是说，`eq()` 是一个实例方法。相等性只依赖于类型 `A` 本身才更合理，对吧? 这正是类型类的用武之地: ```java interface Eq<A> { boolean eq(A x, A y); } record Point(int x, int y) { public static Eq<Point> eq() { return (p1, p2) -> p1.x() == p2.x() && p1.y() == p2.y(); } } record Dup<A>(A fst, A snd) { public static Eq<Dup<A>> eq(Eq<A> eqA) { return (d1, d2) -> eqA.eq(d1.fst(), d2.fst()) && eqA.eq(d1.snd(), d2.snd()); } } ``` 让我们逐一分析: - `Eq<A>` 现在比较的是两个类型为 `A` 的值。 - 这表明我们不再期望隐式的 `this` 参数参与相等性判断。 - `Point` 不再实现该接口。 - 它现在提供一个 `Eq<Point>` 的静态构造函数（工厂方法）。 - 我们称之为 `Point` 符合 `Eq` 的一个**见证**（*witness*）。 - `Dup` 同样不实现该接口。 - 它的 `Eq<Dup<A>>` 静态构造函数有一个类型为 `Eq<A>` 的参数。 - 这表达了我们所寻找的依赖关系: - 为了证明 `Eq<Dup<A>>`，我们必须先证明 `Eq<A>`。 - 它使用见证 `Eq<A> eqA`（包含 `boolean eq(A, A)`）来实现自身预期的行为。 这段代码相当简单，但它标志着视角的巨大转变: 相等性现在属于类型定义本身，而不是对象实例。 那么，类型类到底是什么? 类型类可以看作一种模式，它让我们以一种**类型优先**且**完全可组合**的方式来建模共享行为。 现在，在上面的例子中，我们究竟如何使用 `Dup` 的 `eq()` 呢? ```java Eq<Dup<Point>> pointDupEq = Dup.eq(Point.eq()); pointDupEq.eq(new Point(1, 1), new Point(1, 1)); // 返回: true ``` 我们必须先通过链式调用 `Dup` 和 `Point` 各自的 `Eq` 见证构造函数来构建见证 `Eq<Dup<Point>>`。然后，使用这个见证来访问/调用我们所需的实际逻辑。 注意这个模式的组合性非常好: ```java static <K, V> Eq<Map<K, V>> mapEq(Eq<K> eqK, Eq<V> eqV) { ... } static <A> Eq<List<A>> listEq(Eq<A> eqA); static Eq<Integer> integerEq(); static Eq<String> stringEq(); // 于是: Eq<Map<String, List<Integer>>> eq = mapEq(stringEq(), listEq(integerEq())); Map<String, List<Integer>> m1 = ...; Map<String, List<Integer>> m2 = ...; eq.eq(m1, m2); ``` 有了见证构造函数作为构建块，我们就可以根据需要递归地构造无穷多个见证。 > 关于命名的一点说明: 在 Haskell 中，类型类的"实现"被称为**实例**（*instance*）。而我在这里称之为**见证**（*witness*），因为在 [Brian Goetz 最近关于将类型类引入 Java 的演讲](https://www.youtube.com/watch?v=Gz7Or9C0TpM)中，Java 架构师就是这么称呼它们的。 那么，如果我们不需要手动构造这些见证，那该多好啊！ ## 目标: 以编程方式实例化见证 给定: ```java @TypeClass interface Show<A> { String show(A value); // 便捷方法 static <A> String show(Show<A> showA, A value) { return showA.show(value); } @TypeClass.Witness static Show<Integer> showInteger() { ... } @TypeClass.Witness static <A> Show<List<A>> showList(Show<A> showA) { ... } } ``` 原本我们需要: ```java Show<List<List<Integer>>> w = Show.showList(Show.showList(Show.showInteger())); Show.show(w, List.of(List.of(1, 2), List.of(3, 4))); // 返回: "[[1, 2], [3, 4]]" ``` 而我们想要的是: ```java Show.show(witness(), List.of(List.of(1, 2), List.of(3, 4))); // 返回: "[[1, 2], [3, 4]]" ``` 这意味着 `witness()` 方法能够自动构造 `Show<List<List<Integer>>>` 所需的见证。 我们如何做到这一点? 首先，必须了解 Java 泛型在运行时的一些行为。 ## 补充: Java 泛型与类型擦除 众所周知，Java 泛型在运行时会被擦除。然而，在某些场景中，泛型信息*确实*会被具体化！ > 注: "类型具体化"（Type Reification）是指将类型信息在运行时变得具体且可用的过程。 给定: ```java interface Stream<T> { ... } interface IntStream extends Stream<Integer> { ... } ``` 那么: ```java IntStream.class.getInterfaces()[0]; // 返回: Stream IntStream.class.getGenericInterfaces()[0]; // 返回: Stream<Integer> ``` 这意味着 Java *确实*为超类型 `Stream` 保留了泛型类型参数。（我们只需要知道去哪里找它。） 注意，匿名类也是如此: ```java var s = new Stream<Integer>() { ... }; s.getClass().getGenericInterfaces()[0]; // 返回: Stream<Integer> ``` 这引出了我们的第一个变通方案: ## 补充: 捕获静态类型 我们定义: ```java interface Ty<T> { default Type type() { return requireNonNull( ((ParameterizedType) getClass().getGenericInterfaces()[0]) .getActualTypeArguments()[0]); } } ``` 于是我们可以这样写: ```java Type type = new Ty<Map<String, List<Integer>>>() {}.type(); println(type); // 输出: Map<String, List<Integer>> ``` 为什么我们需要这个? 因为 `witness()` 方法需要一个运行时的类型表示来知道要实例化什么。于是我们的用例变成了: ```java Show.show(witness(new Ty<>() {}), List.of(List.of(1, 2), List.of(3, 4))); ``` 注意，我们不需要为 `Ty<>` 显式指定类型参数。感谢类型推断帮我们完成了这件事。类型推断在这里之所以有效，是因为 `List.of(...)` 参数有明确的类型，并且 `Show.show(Show<A>, A)` 的调用让类型推断可以从第二个参数流向第一个参数。 ## 补充: 理解 `java.lang.reflect.Type` 的层次结构 标准的 `java.lang.reflect.Type` 层次结构包括: - `Class` - `GenericArrayType` - `ParameterizedType` - `TypeVariable` - `WildcardType` 其中: - `Class`，有时被称为"原始类型"（raw type），表示: - 非泛型类型如 `String` 或 `Integer`。 - 泛型类型如 `Function`，其类型参数列表 `[T, R]` 可通过 `TypeVariable[] getTypeParameters()` 获取。 - `GenericArrayType` 表示数组类型 `E[]`，其中元素类型 `E` 是 `ParameterizedType` 或 `TypeVariable`。 - `ParameterizedType` 表示类型 `T<A>`。其 `getRawType()` 方法返回类或接口 `T`。 - `TypeVariable` 表示泛型声明（如泛型类/接口或泛型方法）中的未绑定类型参数。 - `WildcardType` 表示 `ParameterizedType` 中出现的 `?`。 此外，`java.lang.reflect.Method` 可以通过 `TypeVariable[] getTypeParameters()`、`Type[] getGenericParameterTypes()` 和 `Type getGenericReturnType()` 进行查询。 例如: ```java class Example { static <A> List<A> hello(String s, A[] arr, Optional<? extends Number> opt) { ... } } ``` 在运行时检查 `Example` 的 `hello` 方法会得到类似: ``` Method( name: "hello", typeParameters: [TypeVariable(A)], genericReturnType: ParameterizedType( rawType: List.class, typeArguments: [TypeVariable(A)], ), genericParameterTypes: [ String.class, GenericArrayType(componentType: TypeVariable(A)), ParameterizedType( rawType: Optional.class, typeArguments: [WildcardType()] ) ] ) ``` 注意三处 `TypeVariable(A)` 是唯一的，它们互相比较 `equal()` 为 `true`，但与其他 `TypeVariable` 实例即使名称也叫 `A` 时*不相等*。 ## 子目标: 将 `java.lang.reflect.Type` 解析为 AST 我们希望这么做，有几个原因: - `java.lang.reflect.Type` 不便于编程: - 它不是密封层次结构，因此模式匹配容易出错。 - `Class` 和 `GenericArrayType` 都可能表示数组类型。 - `Class` 可能表示基本类型如 `int` 或 `float`，而基本类型（目前）不参与泛型参数化。 - `ParameterizedType` 表示的类型应用是可变参数的。一次处理一个参数更容易编程。 - 当我们涉及高阶类型类（剧透！）时，无论如何都需要自己的类型表示。 以下是 AST: ```java sealed interface ParsedType { record Var(TypeVariable<?> java) implements ParsedType {} record App(ParsedType fun, ParsedType arg) implements ParsedType {} record ArrayOf(ParsedType elementType) implements ParsedType {} record Const(Class<?> java) implements ParsedType {} record Primitive(Class<?> java) implements ParsedType {} } ``` 这是我们的解析规则: ```java sealed interface ParsedType { // ... static ParsedType parse(Type java) { return switch (java) { case Class<?> arr when arr.isArray() -> new ArrayOf(parse(arr.getComponentType())); case Class<?> prim when prim.isPrimitive() -> new Primitive(prim); case Class<?> c -> new Const(c); case TypeVariable<?> v -> new Var(v); case ParameterizedType p -> parseAll(p.getActualTypeArguments()).stream() .reduce(parse(p.getRawType()), App::new); case GenericArrayType a -> new ArrayOf(parse(a.getGenericComponentType())); case WildcardType w -> throw new IllegalArgumentException("Cannot parse wildcard type: " + w); default -> throw new IllegalArgumentException("Unsupported type: " + java); }; } } ``` > 注: `ParameterizedType` 的规则会将 `Map<A, B>` 这样的类型转换为 `App(App(Const(Map), A), B)`。这意味着泛型类型 `Map` 先应用于 `A`，再应用于 `B`。 例如，`Map<Integer, List<String>>` 会变成: ``` App( App(Const(Map.class), Const(Integer.class)), App(Const(List.class), Const(String.class)) ) ``` 就是这样！确实不算多，但这种统一性将在后续代码中帮到我们。 ## 回顾 到目前为止，我们已经有: - `new Ty<>() {}`: 一种从静态上下文捕获类型 `T` 并在运行时访问它的方法。 - `ParsedType`: Java 的 `java.lang.reflect.Type` 的统一表示。 现在，让我们进入类型类实例解析的问题。 ## 子目标: 见证解析 让我们考虑以下场景: ```java @TypeClass interface Show<A> { String show(A value); // 便捷方法 static <A> String show(Show<A> showA, A value) { return showA.show(value); } @TypeClass.Witness static Show<Integer> showInteger() { ... } @TypeClass.Witness static <A> Show<List<A>> showList(Show<A> showA) { ... } } record Pair<A, B>(A fst, B snd) { @TypeClass.Witness public static <A, B> Show<Pair<A, B>> show(Show<A> showA, Show<B> showB) { ... } } ``` 我们观察到，例如，为了召唤 `Show<Pair<Integer, String>>` 的见证，必须递归地应用多个见证构造函数。 > 什么是见证构造函数? 它是一个用 `@TypeClass.Witness` 注解标记的 `public static` 方法……