Full Haskell-like Type Class resolution in Java

⇤ BackDecember 6, 202579 min readTags: Haskell, JavaContents TL;DR Intro: What are Type Classes? Goal: Programmatically instantiating witnesses Aside: Java Generics and Type Erasure Aside: Capturing static types Aside: Understanding java.lang.reflect.Type's hierarchy Subgoal: Parsing java.lang.reflect.Type into an AST Recap Subgoal: Witness resolution Aside: Type Unification Listing: Type Unification algorithm for ParsedType Extra: A type representation for static methods Subgoal: Witness resolution, part 2 Recap Subgoal: Witness resolution implementation Examples: First-Order Type Classes & Instances Type Class: Show Type Class: Monoid & Num Type Class: PrintAll Type Class: Type Equality! Goal: Higher-Order Type Classes Aside: What is a kind? Aside: Higher-Kinded Types in Java Subgoal: Extending ParsedType to support HKTs Aside: Kind-checking Java-embedded HKTs Examples: Higher-Kinded Type Clases Type Class: Traversable Type Class: Functor, Applicative, Monad Recap Conclusion Future work Related Work Annex: Context Instances Annex: Overlapping Instances TL;DR This post explores how far Java’s type system can be pushed by building a small Haskell-style type class instance resolution engine entirely in plain Java. Using only reflection, generic type metadata, and a tiny first-order unifier, we can automatically resolve type class instances (including higher-kinded ones), support overlapping instances, and derive witnesses for arbitrarily nested generic types. It’s not intended for production, but as an experiment it reveals just how much structure Java actually preserves at runtime — and how surprisingly close it can get to type-level programming without language changes. You can also jump straight to the full implemention in this gist. Update: I published a GitHub repo for the project at github.com/garciat/java-type-classes. Intro: What are Type Classes? Consider: 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(); } } That's a pretty simple OOP-style generic interface. However: 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()); // Error: no method eq() in type A! } } We can't implement eq() for Dup without knowing the fact that A extends Equatable<A>. So let's try that: record Dup<A extends Equatable<A>>(A …