{"article":{"slug":"full-haskell-like-type-class-resolution-in-java","title":"Full Haskell-like Type Class resolution in Java","subtitle":null,"summary":"Gabriel Garcia re-implements Haskell-style type classes in pure Java: using reflection and generics to parse static types, unify them, and automatically resolve instance witnesses, then extends the approach to higher-kinded types, context instances and overlapping instances, with worked examples like Show, Monoid, Traversable and Monad.","content_type":"tutorial","language":"en","canonical_url":"https://garciat.com/posts/java-type-classes/","author":{"name":"Gabriel Garcia","url":"https://garciat.com/","person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"garciat.com","url":"https://garciat.com/","listing_slug":null,"listing":null},"topics":[{"name":"Programming Languages","slug":"programming-languages","url":"https://listedarticles.com/topics/programming-languages"},{"name":"Java","slug":"java","url":"https://listedarticles.com/topics/java"},{"name":"Haskell","slug":"haskell","url":"https://listedarticles.com/topics/haskell"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":7285,"reading_minutes":32,"published_at":"2025-12-06T00:00:00.000Z","added_at":"2026-10-27T11:12:36.530Z","updated_at":"2026-10-27T11:12:36.530Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/full-haskell-like-type-class-resolution-in-java","markdown_url":"https://listedarticles.com/articles/full-haskell-like-type-class-resolution-in-java.md","example":false,"citation":"Gabriel Garcia, garciat.com. \"Full Haskell-like Type Class resolution in Java.\" 6 Dec 2025. https://garciat.com/posts/java-type-classes/ (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://garciat.com/posts/java-type-classes/"},"body_markdown":"# Full Haskell-like Type Class resolution in Java\n\n*Gabriel Garcia · December 6, 2025*\n\n## TL;DR\n\nThis post explores how far Java’s type system can be pushed by building a small\nHaskell-style type class instance resolution engine entirely in plain Java.\n\nUsing only reflection, generic type metadata, and a tiny first-order unifier, we\ncan automatically resolve type class instances (including higher-kinded ones),\nsupport overlapping instances, and derive witnesses for arbitrarily nested\ngeneric types.\n\nIt’s not intended for production, but as an experiment it reveals just how much\nstructure Java actually preserves at runtime — and how surprisingly close it can\nget to type-level programming without language changes.\n\nYou can also jump straight to the full implemention\n[in this gist](https://gist.github.com/Garciat/204226a528018fa7d10abb93fa51c4ca).\n\nUpdate: I published a GitHub repo for the project at\n[github.com/garciat/java-type-classes](https://github.com/garciat/java-type-classes).\n\n## Intro: What are Type Classes?\n\nConsider:\n\n```\ninterface Equatable {\n boolean eq(T other);\n}\n\nrecord Point(int x, int y) implements Equatable {\n @Override\n public boolean eq(Point other) {\n return x == other.x() && y == other.y();\n }\n}\n```\n\nThat's a pretty simple OOP-style generic interface.\n\nHowever:\n\n```\nrecord Dup(A fst, A snd) implements Equatable> {\n @Override\n public boolean eq(Dup other) {\n return fst.eq(other.fst()) && snd.eq(other.snd());\n // Error: no method eq() in type A!\n }\n}\n```\n\nWe can't implement `eq()` for `Dup` without knowing the fact that\n`A extends Equatable`.\n\nSo let's try that:\n\n```\nrecord Dup>(A fst, A snd) implements Equatable> {\n @Override\n public boolean eq(Dup other) {\n return fst.eq(other.fst()) && snd.eq(other.snd());\n // OK\n }\n}\n```\n\nNow the code compiles.\n\nHowever, `Dup` is now only compatible with types that extend `Equatable`. `Dup`\nis now less capable.\n\nWe could have checked at runtime if each object is `instanceof Equatable`, but\nthat doesn't work very well with generics. And it may fail at runtime.\n\nIdeally, there would be a way to say:\n\n`Dup` implements `Equatable>` **if and only if** `A` implements\n`Equatable`.\n\n> Also, if you think about it, it is a bit strange that the definition of\n> equality for a type `A` depends on the object instance. As in, `eq()` is an\n> instance method.\n>\n> It would make more sense if equality depended only on the type `A` itself.\n> Right?\n\nThat's where type clases come in:\n\n```\ninterface Eq {\n boolean eq(A x, A y);\n}\n\nrecord Point(int x, int y) {\n public static Eq eq() {\n return (p1, p2) ->\n p1.x() == p2.x()\n && p1.y() == p2.y();\n }\n}\n\nrecord Dup(A fst, A snd) {\n public static Eq> eq(Eq eqA) {\n return (d1, d2) ->\n eqA.eq(d1.fst(), d2.fst())\n && eqA.eq(d1.snd(), d2.snd());\n }\n}\n```\n\nLet's unpack this:\n\n- `Eq` now compares two values of type `A`.\n - This indicates that we are no longer expecting the implicit `this` parameter\n to be relevant in equality.\n- `Point` no longer implements the interface.\n - Now it provides a static constructor (factory) for `Eq`.\n - We call this a *witness* that `Point` conforms to `Eq`.\n- `Dup` also does not implement the interface.\n - Its static constructor for `Eq>` has a parameter of type `Eq`.\n - This indicates the dependency that we were looking for:\n - In order to prove `Eq>`, we must first prove `Eq`.\n - It uses the witness `Eq eqA`, which contains `boolean eq(A, A)`, to\n implement its own intended behavior.\n\nThe code is rather simple, but it marks a dramatic change of perspective:\n\nEquality now belongs to the type definition and not to an object instance.\n\nSo, what are type classes?\n\nType classes can be seen as a pattern that allows us to model shared behavior in\na way that puts types first AND is entirely compositional.\n\nNow, in the above example, how do we actually use `Dup`'s `eq()`?\n\n```\nEq> pointDupEq = Dup.eq(Point.eq());\n\npointDupEq.eq(new Point(1, 1), new Point(1, 1));\n// Returns: true\n```\n\nWe must first construct the witness `Eq>` by chaining calls to the\nrespective `Eq` witness constructors of `Dup` and `Point`.\n\nThen, we use this witness to access/invoke the actual logic that we're after.\n\nNotice how this pattern composes very nicely:\n\n```\nstatic Eq> mapEq(Eq eqK, Eq eqV) { ... }\n\nstatic Eq> listEq(Eq eqE);\n\nstatic Eq integerEq();\n\nstatic Eq stringEq();\n\n// then:\n\nEq>> eq =\n mapEq(stringEq(), listEq(integerEq()));\n\nMap> m1 = ...;\nMap> m2 = ...;\n\neq.eq(m1, m2);\n```\n\nWith witness constructors as our building blocks, we can recursively construct\ninfinitely many witnesses, as needed.\n\n> A note on nomenclature:\n>\n> In Haskell, type class 'implementations' are called *instances*.\n>\n> Here, I am calling them *witnesses* because that's how Java's Architect, Brian\n> Goetz, decided to refer to them in\n> [a recent talk](https://www.youtube.com/watch?v=Gz7Or9C0TpM) he gave about\n> bringing type classes to Java sometime in the future.\n\nNow, wouldn't it be great if we didn't have to manually construct these\nwitnesses?\n\n## Goal: Programmatically instantiating witnesses\n\nGiven:\n\n```\n@TypeClass\ninterface Show {\n String show(A value);\n\n // Convenience shortcut\n static String show(Show showA, A value) {\n return showA.show(value);\n }\n\n @TypeClass.Witness\n static Show showInteger() { ... }\n\n @TypeClass.Witness\n static Show> showList(Show showA) { ... }\n}\n```\n\nInstead of:\n\n```\nShow>> w =\n Show.showList(Show.showList(Show.showInteger()));\n\nShow.show(w, List.of(List.of(1, 2), List.of(3, 4)));\n// Returns: \"[[1, 2], [3, 4]]\"\n```\n\nWe want:\n\n```\nShow.show(witness(), List.of(List.of(1, 2), List.of(3, 4)));\n// Returns: \"[[1, 2], [3, 4]]\"\n```\n\nWhich means that the `witness()` method is able to automatically construct the\nrequired witness for `Show>>`.\n\nHow do we get there?\n\nFirst, we must understand some aspects of how Java generics work at runtime.\n\n## Aside: Java Generics and Type Erasure\n\nIt is a well-known fact that Java generics get erased at runtime.\n\nHowever, there are a few scenarios in which generics *do* get reified!\n\n> Note: 'Type Reification' is the process by which type information is made\n> concrete and available at runtime.\n\nGiven:\n\n```\ninterface Stream { ... }\n\ninterface IntStream extends Stream { ... }\n```\n\nThen:\n\n```\nIntStream.class.getInterfaces()[0];\n// Returns: Stream\n\nIntStream.class.getGenericInterfaces()[0];\n// Returns: Stream\n```\n\nThis means that Java *did* preserve the generic type arguments for the supertype\n`Stream`. (We just need to know where to look for it.)\n\nNote that this also occurs with anonymous classes:\n\n```\nvar s = new Stream() { ... };\n\ns.getClass().getGenericInterfaces()[0];\n// Returns: Stream\n```\n\nThis leads us to our first workaround:\n\n## Aside: Capturing static types\n\nWe define:\n\n```\ninterface Ty {\n default Type type() {\n return requireNonNull(\n ((ParameterizedType) getClass().getGenericInterfaces()[0])\n .getActualTypeArguments()[0]);\n }\n}\n```\n\nWhich lets us write:\n\n```\nType type = new Ty>>() {}.type();\n\nprintln(type);\n// Prints: Map>\n```\n\nWhy do we need this?\n\nBecause our `witness()` method will need a runtime representation of the type\nthat it is trying to instantiate.\n\nSo our use case has turned into:\n\n```\nShow.show(witness(new Ty<>() {}), List.of(List.of(1, 2), List.of(3, 4)));\n```\n\nNote that we do not have to specify the type argument for `Ty<>`. Thankfully,\ntype inference does that for us.\n\nType inference works in this case because the `List.of(...)` parameter has a\nwell-defined type, and the call to ` Show.show(Show, A)` lets type\ninference flow from the second argument to the first.\n\n## Aside: Understanding `java.lang.reflect.Type`'s hierarchy\n\nThe standard `java.lang.reflect.Type` hierarchy consists of:\n\n- `Class`\n- `GenericArrayType`\n- `ParameterizedType`\n- `TypeVariable`\n- `WildcardType`\n\nWhere:\n\n- `Class`, sometimes referred to as a 'raw type', represents either:\n - A non-generic type like `String` or `Integer`.\n - A generic type like `Function` where its type parameter list `[T, R]`\n can be retrieved via `TypeVariable[] getTypeParameters()`.\n- `GenericArrayType` represents an array type `E[]` whose component type `E` is\n a `ParameterizedType` or a `TypeVariable`.\n- `ParameterizedType` represents a type `T`. Its\n `getRawType()` method returns the class or interface `T`.\n- `TypeVariable` represents an unbound type parameter of a generic\n declaration like a generic class/interface or generic method.\n- `WildcardType` represents an occurrence of `?` within a `ParameterizedType`.\n\nMoreover, a `java.lang.reflect.Method` can be queried via\n`TypeVariable[] getTypeParameters()`, `Type[] getGenericParameterTypes()`,\nand `Type getGenericReturnType()`.\n\nFor example:\n\n```\nclass Example {\n static List hello(String s, A[] arr, Optional opt) { ... }\n}\n```\n\nInspecting the `Example`'s `hello` method at runtime would yield something like:\n\n```\nMethod(\n name: \"hello\",\n typeParameters:\n [TypeVariable(A)],\n genericReturnType:\n ParameterizedType(\n rawType: List.class,\n typeArguments: [TypeVariable(A)],\n ),\n genericParameterTypes:\n [\n String.class,\n GenericArrayType(componentType: TypeVariable(A)),\n ParameterizedType(\n rawType: Optional.class,\n typeArguments: [WildcardType()]\n )\n ]\n)\n```\n\nNote that the three ocurrences of `TypeVariable(A)` are unique in the sense that\nthey compare `equal()` to each other, but *not* to other type variable\ninstances, even if their names are also `A`.\n\n## Subgoal: Parsing `java.lang.reflect.Type` into an AST\n\nWe want to do this for a few reasons:\n\n- `java.lang.reflect.Type` is not convenient for programming:\n - It is not a sealed hierarchy, so pattern-matching on it is error-prone.\n - Both `Class` and `GenericArrayType` may be array types.\n - `Class` may represent a primitive type, like `int` or `float`, which does\n not participate in generic parameterization (yet).\n - Type application as represented by `ParameterizedType` is variadic.\n Single-parameter-a-time is easier to program against.\n- When we get to higher-kinded type classes (spoiler!), then we will need our\n own type representation anyway.\n\nHere's the AST:\n\n```\nsealed interface ParsedType {\n record Var(TypeVariable java) implements ParsedType {}\n\n record App(ParsedType fun, ParsedType arg) implements ParsedType {}\n\n record ArrayOf(ParsedType elementType) implements ParsedType {}\n\n record Const(Class java) implements ParsedType {}\n\n record Primitive(Class java) implements ParsedType {}\n}\n```\n\nAnd these are our parsing rules:\n\n```\nsealed interface ParsedType {\n // ...\n\n static ParsedType parse(Type java) {\n return switch (java) {\n case Class arr when arr.isArray() ->\n new ArrayOf(parse(arr.getComponentType()));\n case Class prim when prim.isPrimitive() ->\n new Primitive(prim);\n case Class c ->\n new Const(c);\n case TypeVariable v ->\n new Var(v);\n case ParameterizedType p ->\n parseAll(p.getActualTypeArguments()).stream()\n .reduce(parse(p.getRawType()), App::new);\n case GenericArrayType a ->\n new ArrayOf(parse(a.getGenericComponentType()));\n case WildcardType w ->\n throw new IllegalArgumentException(\"Cannot parse wildcard type: \" + w);\n default ->\n throw new IllegalArgumentException(\"Unsupported type: \" + java);\n };\n }\n}\n```\n\n> Note: the rule for `ParameterizedType` will take a type like `T` and\n> turn it into `App(App(Const(T), A), B)`.\n>\n> This means that the generic type `T` is first applied to `A` and then to `B`.\n\nFor example, `Map>` becomes:\n\n```\nApp(\n App(Const(Map.class), Const(Integer.class)),\n App(Const(List.class), Const(String.class))\n)\n```\n\nThat's it! Really, it's not much, but the added uniformity will help our code\ndown the line.\n\n## Recap\n\nUntil this point we have:\n\n- `new Ty() {}`: a way to capture a type `T` from a static context and access\n it at runtime.\n- `ParsedType`: a uniform representation for Java's `java.lang.reflect.Type`s.\n\nNow, let's move on to the problem of type class instance resolution.\n\n## Subgoal: Witness resolution\n\nLet's consider the following scenario:\n\n```\n@TypeClass\ninterface Show {\n String show(A value);\n\n // Convenience shortcut\n static String show(Show showA, A value) {\n return showA.show(value);\n }\n\n @TypeClass.Witness\n static Show showInteger() { ... }\n\n @TypeClass.Witness\n static Show> showList(Show showA) { ... }\n}\n\nrecord Pair(A fst, B snd) {\n @TypeClass.Witness\n public static Show> show(Show showA, Show showB) { ... }\n}\n```\n\nWe observe that, for example, in order to summon a witness for\n`Show>>`, then we must apply several witness\nconstructors recursively.\n\n> What is a witness constructor? It is a `public static` method annotated with\n> `@TypeClass.Witness`.\n\nBut first, we must find the witness constructors!\n\nHow do we do that? Do we need to do a runtime scan of all loaded classes?\n\nThat would be way too complicated.\n\nIn order to reduce our search scope, we can define the following convention:\n\n> When trying to resolve a witness `C` for some type class `C` and a concrete\n> type `T`, then we only look for witness constructors within the definitions of\n> `C` and `T` and nowhere else.\n\nFor example, when looking for `Show`, then we scan the methods of\n`Show` and `Integer`.\n\nGenerally, we will prefer to define witness constructors within concrete types\nand not within type classes. However, for a built-in type like `Integer`, we\nhave no choice and we must define its witness constructors within the relevant\ntype classes, as we have done with `static Show showInteger()`.\n\nNow that we are able to find the relevant witness constructors, how do we:\n\n- know which of them we must invoke,\n- and in *which order*?\n\nFirst, we must understand type unification:\n\n## Aside: Type Unification\n\nType unification is the process of finding a substitution that makes two types\nidentical.\n\nFor example, given `Pair<[A], String>` and `Pair`, then the\nsubstitution `{A -> Integer}` would make the first type identical to the second.\n\n> Here, I have placed the type `A` between square brackets to indicate that it\n> is a *type variable*. We only substitute type variables!\n\nUnification may fail when it encounters incompatible types. For example,\n`List` and `List` cannot be unified because no substitution\nexists that would make them identical.\n\nConversely, when two types are already identical, unification succeeds with an\nempty substitution `{}`.\n\nBecause types are recursive, the unification algorithm must also be recursive\n(in nature).\n\nConsider:\n\n```\nunify(\n Map, List<[U]>>,\n Map, List>>\n)\n\n// we are unifying two types of shape:\n// - Map\n// - Map\n// the type constructors match on either side (Map)\n// so we recurse to their type arguments:\n// unify(K1, K2) ∪ unify(V1, V2)\n// and so on!\n\n= unify(Pair, Pair)\n ∪ unify(List<[U]>, List>)\n\n= unify(String, String) // first arguments of Pair\n ∪ unify([T], Integer) // second arguments of Pair\n ∪ unify([U], ) // arguments of List\n\n= {}\n ∪ {T -> Integer}\n ∪ {U -> Optional}\n\n= {T -> Integer, U -> Optional}\n\n// Done!\n```\n\nIf any unification step fails, then the entire unification fails:\n\n```\nunify(Pair<[T], Integer>, Pair)\n\n= unify([T], String)\n ∪ unify(Integer, String)\n\n= {T -> String}\n ∪ err\n\n= err\n```\n\nFollowing is a code listing for the concrete type unification algorithm\n`unify()` for our `ParsedType` definition, along with a `subsitute()` method\nthat applies a substitution to a type.\n\n### Listing: Type Unification algorithm for `ParsedType`\n\nHere we use the `Maybe` type, which is analogous to Java's `Optional`. It is\nused to indicate that the `unify()` function may fail with a `nothing()` (empty)\ncase. This is different from it returning `just(Map.of())` (an empty map), which\nsignals success but without any substitutions. In short, based on the examples\nabove, `err` is `nothing()` and `{}` is `just(Map.of())`.\n\nA key step here is the unification of `App`. This is the main driver for the\nalgorithm's recursion.\n\nThe following helper methods are relevant to this step:\n\n```\n// applies function `f` if both `ma` and `mb` are present\n Maybe apply(BiFunction f, Maybe ma, Maybe mb);\n\n// merges two maps\n// it fails at runtime if duplicate keys /with different values/ exist\n Map merge(Map m1, Map m2);\n```\n\nHere's the full code:\n\n```\nclass Unification {\n public static Maybe> unify(ParsedType t1, ParsedType t2) {\n return switch (Pair.of(t1, t2)) {\n case Pair(ParsedType.Var var1, ParsedType.Primitive p) ->\n Maybe.nothing(); // no primitives in generics\n case Pair(ParsedType.Var var1, var t) ->\n Maybe.just(Map.of(var1, t));\n case Pair(ParsedType.Const const1, ParsedType.Const const2)\n when const1.equals(const2) ->\n Maybe.just(Map.of());\n case Pair(\n ParsedType.App(var fun1, var arg1),\n ParsedType.App(var fun2, var arg2)) ->\n Maybe.apply(Maps::merge, unify(fun1, fun2), unify(arg1, arg2));\n case Pair(\n ParsedType.ArrayOf(var elem1),\n ParsedType.ArrayOf(var elem2)) ->\n unify(elem1, elem2);\n case Pair(\n ParsedType.Primitive(var prim1),\n ParsedType.Primitive(var prim2))\n when prim1.equals(prim2) ->\n Maybe.just(Map.of());\n default ->\n Maybe.nothing();\n };\n }\n\n public static ParsedType substitute(Map map, ParsedType type) {\n return switch (type) {\n case ParsedType.Var var ->\n map.getOrDefault(var, var);\n case ParsedType.App(var fun, var arg) ->\n new ParsedType.App(substitute(map, fun), substitute(map, arg));\n case ParsedType.ArrayOf var ->\n new ParsedType.ArrayOf(substitute(map, var.elementType()));\n case ParsedType.Primitive p ->\n p;\n case ParsedType.Const c ->\n c;\n };\n }\n\n public static List substituteAll(\n Map map, List types) {\n return types.stream().map(t -> substitute(map, t)).toList();\n }\n}\n```\n\n### Extra: A type representation for static methods\n\n```\nrecord FuncType(Method java, List paramTypes, ParsedType returnType) {\n public static FuncType parse(Method method) {\n if (!Modifier.isStatic(method.getModifiers())) {\n throw new IllegalArgumentException(\"Method must be static: \" + method);\n }\n return new FuncType(\n method,\n ParsedType.parseAll(method.getGenericParameterTypes()),\n ParsedType.parse(method.getGenericReturnType()));\n }\n}\n```\n\n## Subgoal: Witness resolution, part 2\n\nWhy is type unification relevant?\n\nType unification will guide the witness resolution process in two ways:\n\n- By checking if any given witness constructor is relevant to our witness goal.\n- And if it *is* relevant, then it will tell us which witness subgoals to\n resolve next.\n\nFor example, when resolving `Show>`, we check:\n\n1. Which witness constructors can we find?\n\n- We scan `List`:\n - It contains zero witness constructors.\n- We scan `Show`, and it contains:\n - `Show showInteger()`\n - ` Show> showList(Show showA)`\n\n2. Which witness constructors apply to our goal?\n\n- Does `Show showInteger()` apply?\n - We try to unify `Show` and `Show>`.\n - Unification fails.\n - Skip this constructor ❌\n- Does ` Show> showList(Show showA)` apply?\n - We try to unify `Show>` and `Show>`.\n - Unification succeeds with the substitution `{A -> Integer}`.\n - We can use this constructor ✅\n - But this constructor has an argument: `Show`\n - If we apply the substitution to the argument, we find our next goal:\n - `substitute({A -> Integer}, Show)` yields `Show`.\n - Add `Show` to our goals.\n\n3. Recurse until we have no further goals.\n\nThat outlines the witness resolution algorithm.\n\n## Recap\n\nUntil this point we have:\n\n- `new Ty() {}`: a way to capture a type `T` from a static context and access\n it at runtime.\n- `ParsedType`: a uniform representation for Java's `java.lang.reflect.Type`s.\n- `Unification`: an algorithm for type unification of `ParsedType`s.\n- And a rough sketch for the overall recursive witness resolution algorithm.\n\nNow, let's put it all together!\n\n## Subgoal: Witness resolution implementation\n\nLet's start with the witness constructor lookup code:\n\n```\n@Retention(RetentionPolicy.RUNTIME)\n@interface TypeClass {\n @Retention(RetentionPolicy.RUNTIME)\n @interface Witness {}\n}\n\nclass TypeClasses {\n // ...\n\n private static List findRules(ParsedType target) {\n return switch (target) {\n case ParsedType.App(var fun, var arg) ->\n Lists.concat(findRules(fun), findRules(arg));\n case ParsedType.Const(var java) ->\n rulesOf(java);\n case ParsedType.Var(var java) ->\n List.of();\n case ParsedType.ArrayOf(var elem) ->\n List.of();\n case ParsedType.Primitive(var java) ->\n List.of();\n };\n }\n\n private static List rulesOf(Class cls) {\n return Arrays.stream(cls.getDeclaredMethods())\n .filter(TypeClasses::isWitnessMethod)\n .map(FuncType::parse)\n .map(InstanceConstructor::new)\n .toList();\n }\n\n private static boolean isWitnessMethod(Method m) {\n return m.accessFlags().contains(PUBLIC)\n && m.accessFlags().contains(STATIC)\n && m.isAnnotationPresent(TypeClass.Witness.class);\n }\n\n private record InstanceConstructor(FuncType func) {}\n\n // ...\n}\n```\n\nNow, let's move on to how we choose relevant witness constructors and find our\nsubsequent goals:\n\n```\nclass TypeClasses {\n // ...\n\n private static List findCandidates(ParsedType target) {\n return findRules(target).stream()\n .flatMap(\n rule ->\n rule\n .tryMatch(target)\n .map(requirements -> new Candidate(rule, requirements))\n .stream())\n .toList();\n }\n\n private record Candidate(WitnessRule rule, List requirements) {}\n\n // Spoiler: we will have another subtype of WitnessRule later on (;\n private sealed interface WitnessRule {\n Maybe> tryMatch(ParsedType target);\n\n Object instantiate(List dependencies);\n }\n\n private record InstanceConstructor(FuncType func) implements WitnessRule {\n @Override\n public Maybe> tryMatch(ParsedType target) {\n return Unification.unify(func.returnType(), target)\n .map(map -> Unification.substituteAll(map, func.paramTypes()));\n }\n\n @Override\n public Object instantiate(List dependencies) {\n try {\n return func.java().invoke(null, dependencies.toArray());\n } catch (Exception e) {\n throw new RuntimeException(e);\n }\n }\n }\n\n // ...\n}\n```\n\nThen, the code that drives the recursive resolution:\n\n```\nclass TypeClasses {\n // ...\n\n private static Either summon(ParsedType target) {\n return switch (ZeroOneMore.of(findCandidates(target, context))) {\n case ZeroOneMore.One(Candidate(var rule, var requirements)) ->\n summonAll(requirements, context)\n .map(rule::instantiate)\n .mapLeft(error -> new SummonError.Nested(target, error));\n case ZeroOneMore.Zero() ->\n Either.left(new SummonError.NotFound(target));\n case ZeroOneMore.More(var candidates) ->\n Either.left(new SummonError.Ambiguous(target, candidates));\n };\n }\n\n private static Either> summonAll(List targets) {\n return Either.traverse(targets, TypeClasses::summon);\n }\n\n private sealed interface SummonError {\n record NotFound(ParsedType target) implements SummonError {}\n\n record Ambiguous(ParsedType target, List candidates) implements SummonError {}\n\n record Nested(ParsedType target, SummonError cause) implements SummonError {}\n }\n\n // ...\n}\n```\n\nAnd, finally, the public entry point for all of it:\n\n```\nclass TypeClasses {\n public static T witness(Ty ty) {\n return switch (summon(ParsedType.parse(ty.type()))) {\n case Either.Left(SummonError error) ->\n throw new WitnessResolutionException(error);\n case Either.Right(Object instance) -> {\n @SuppressWarnings(\"unchecked\")\n T typedInstance = (T) instance;\n yield typedInstance;\n }\n };\n }\n\n public static class WitnessResolutionException extends RuntimeException {\n private WitnessResolutionException(SummonError error) {\n super(error.format());\n }\n }\n\n // ...\n}\n```\n\nSurprinsingly, that's it!\n\nYou can find a *mostly accurate* compilation of all of the above code in\n[this Gist](https://gist.github.com/Garciat/a6ca3c9195d5b1d997badecd73282e38).\n(This was the first version of the type class system that I built.)\n\nNow, let's see it in action.\n\n## Examples: First-Order Type Classes & Instances\n\n### Type Class: Show\n\nGiven:\n\n```\n@TypeClass\ninterface Show {\n String show(A a);\n\n static String show(Show showA, A a) {\n return showA.show(a);\n }\n\n @TypeClass.Witness\n static Show integerShow() {\n return i -> Integer.toString(i);\n }\n\n @TypeClass.Witness\n static Show stringShow() {\n return s -> \"\\\"\" + s + \"\\\"\";\n }\n\n @TypeClass.Witness\n static Show> optionalShow(Show showA) {\n return optA -> optA.map(a -> \"Some(\" + showA.show(a) + \")\").orElse(\"None\");\n }\n\n @TypeClass.Witness\n static Show> listShow(Show showA) { ... }\n\n @TypeClass.Witness\n static Show> mapShow(Show showK, Show showV) { ... }\n}\n```\n\nThen:\n\n```\nMap>> m1 =\n Map.of(\n \"a\", List.of(Optional.of(1), Optional.empty()),\n \"b\", List.of(Optional.of(2), Optional.of(3)));\n\nprintln(Show.show(witness(new Ty<>() {}), m1));\n// Prints: {\"a\": [Some(1), None], \"b\": [Some(2), Some(3)]}\n```\n\nNote that this requires the recursive instantiation of 5 witness constructors.\nHere's what some debug logs show:\n\n```\nInstantiating: () -> Show[A](String)\nInstantiating: () -> Show[A](Integer)\nInstantiating: ∀ A. (Show[A](A)) -> Show[A](Optional[T](A))\nInstantiating: ∀ A. (Show[A](A)) -> Show[A](List[E](A))\nInstantiating: ∀ K V. (Show[A](K), Show[A](V)) -> Show[A](Map[K, V](K)(V))\n```\n\n### Type Class: Monoid & Num\n\nGiven:\n\n```\n@TypeClass\ninterface Monoid {\n A combine(A a1, A a2);\n\n A identity();\n\n static A combineAll(Monoid monoid, List elements) {\n A result = monoid.identity();\n for (A element : elements) {\n result = monoid.combine(result, element);\n }\n return result;\n }\n}\n\n@TypeClass\ninterface Num {\n A add(A a1, A a2);\n\n A mul(A a1, A a2);\n\n A zero();\n\n A one();\n\n @TypeClass.Witness\n static Num integerNum() {\n return new Num<>() {\n @Override\n public Integer add(Integer a1, Integer a2) {\n return a1 + a2;\n }\n\n @Override\n public Integer mul(Integer a1, Integer a2) {\n return a1 * a2;\n }\n\n @Override\n public Integer zero() {\n return 0;\n }\n\n @Override\n public Integer one() {\n return 1;\n }\n };\n }\n}\n\nrecord Sum(A value) {\n @TypeClass.Witness\n public static Monoid> monoid(Num num) {\n return new Monoid<>() {\n @Override\n public Sum combine(Sum s1, Sum s2) {\n return new Sum<>(num.add(s1.value(), s2.value()));\n }\n\n @Override\n public Sum identity() {\n return new Sum<>(num.zero());\n }\n };\n }\n}\n```\n\nThen:\n\n```\nvar sums = List.of(new Sum<>(3), new Sum<>(5), new Sum<>(10));\n\nprintln(Monoid.combineAll(witness(new Ty<>() {}), sums));\n// Prints: Sum[value=18]\n```\n\n### Type Class: PrintAll\n\nThis example is based on:\n\n\nIt abuses type classes in order to implement variadic functions. Please read the\nlink above to understand how this works.\n\nIt's really striking how it *just works* with our system!\n\nGiven:\n\n```\n@TypeClass\ninterface PrintAll {\n T printAll(List strings);\n\n static T of(PrintAll printAll) {\n return printAll.printAll(List.of());\n }\n\n @TypeClass.Witness\n static PrintAll base() {\n return strings -> {\n for (String s : strings) {\n System.out.println(s);\n }\n return null;\n };\n }\n\n @TypeClass.Witness\n static PrintAll> func(Show showA, PrintAll printR) {\n return strings -> a -> printR.printAll(Lists.concat(strings, List.of(showA.show(a))));\n }\n}\n```\n\nThen:\n\n```\nFunction, Function>> printer =\n PrintAll.of(witness(new Ty<>() {}));\n\nprinter.apply(\"Items:\").apply(JavaList.of(\"apple\", \"banana\", \"cherry\")).apply(42);\n// Prints:\n// \"Items:\"\n// [\"apple\", \"banana\", \"cherry\"]\n// 42\n```\n\n### Type Class: Type Equality!\n\nThis examples shows how we can encode propositions about types themselves and\nhave the resolver construct evidence for them.\n\nReified type equality is very neat construct that I'd like to write more about\nsoon.\n\nFor now, let's appreciate how this neatly encodes\n[Haskell's own type equality](https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Type-Equality.html)\nin Java.\n\nConsider:\n\n```\n@TypeClass\nsealed interface TyEq {\n A castR(B b);\n\n B castL(A a);\n\n @TypeClass.Witness\n static TyEq refl() {\n return new Refl<>();\n }\n\n record Refl() implements TyEq {\n\n @Override\n public T castR(T t) {\n return t;\n }\n\n @Override\n public T castL(T t) {\n return t;\n }\n }\n}\n```\n\n`TyEq` represents the proposition that `A = B`.\n\nAnd the only possible constructor for it is `refl()`, which can only prove that\n`TyEq` for any `T`.\n\nHow is that useful?\n\n`TyEq` may be trivial in the static context where it is constructed. But\nit certainly is not in the context where it may be needed.\n\nTake a look:\n\n```\nclass List {\n // ...\n\n int sum(TyEq ty) {\n int s = 0;\n for (T item : this) {\n s += ty.castL(item); // casts T to Integer !\n }\n return s;\n }\n\n // ...\n}\n\n// then\n\nvar xs = List.of(1, 2, 3);\n\nxs.sum(refl());\n// Returns: 6\n```\n\nWithin `List`, we have no idea what `T`. Code can make no assumptions about\nit. However, if we have a proof that `T = Integer`, then we *can* sum the\nelements up into an `int`.\n\nNow, we can also request them as witnesses in a witness constructor:\n\n```\n@TypeClass\ninterface SumAllInt {\n A sum(List list);\n\n static T of(SumAllInt sumAllInt) {\n return sumAllInt.sum(List.of());\n }\n\n @TypeClass.Witness\n static SumAllInt base() {\n return list -> list.stream().mapToInt(Integer::intValue).sum();\n }\n\n @TypeClass.Witness\n static SumAllInt> func(TyEq eq, SumAllInt sumR) {\n return list -> a -> sumR.sum(Lists.concat(list, List.of(eq.castL(a))));\n }\n}\n```\n\nSimilar to the `PrintAll` example, this lets us summon variadic functions:\n\n```\nFunction>> sum =\n SumAllInt.of(witness(new Ty<>() {}));\nprintln(sum.apply(1).apply(2).apply(3));\n```\n\nHowever, notice how in the `func` rule, we requested `TyEq`. This\nconstrains the `A` type argument to just `Integer`.\n\nFunny enough, this is actually only necessary in Haskell due to how integer\nliterals are overloaded. So I implemented this here for no gain. But it was cool\nthat it just worked!\n\n## Goal: Higher-Order Type Classes\n\nConsider the `Functor` type class in Haskell:\n\n```\nclass Functor f where\n fmap :: (a -> b) -> f a - > f b\n```\n\nNotice how `f` is not a type?\n\nIt is not one because it is being applied to types `a` and `b`, respectively.\n\nThis means that `f` is a *type constructor*.\n\n> A type constructor is a sort of type-level *function* that builds new types\n> from existing types.\n>\n> Here, we mean *function* in the sense that it has the mathematical property of\n> being *injective*. That is, no two inputs map to the same output.\n>\n> In practice, this means that if we know that the output is the same, then the\n> input must be the same:\n>\n> `F = F ⇒ X = Y`\n>\n> This property is what allows us to unify under type constructors.\n\nIn Java, `class List` can be seen as a type constructor. Though we don't use\ntype application syntax as in Haskell, we do use type parameterization syntax:\n`List`. In Java, generic types cannot be partially applied. That is,\nfor a type `class C`, we must provide all `N` type arguments at\nonce.\n\nLet's try representing the `Functor` type class with a Java interface:\n\n```\ninterface Functor {\n F fmap(Function f, F fa);\n}\n```\n\nUh-oh:\n\n```\nThe type F is not generic; it cannot be parameterized with arguments \n```\n\nIndeed, Java requires that the type parameter `F` is a *type*, and **not a type\nconstructor**.\n\nAre we cooked?\n\nNot quite.\n\n## Aside: What is a kind?\n\nSimply: values have types; types have kinds.\n\n`42` has type `Integer`.\n\n`Integer` has kind `*` (read: star).\n\n> The syntax `*` for the kind of plain types comes from Haskell.\n>\n> We could also say `Integer` has kind `Type`, but that may be confusing given\n> how overloaded the word 'type' is in this context.\n\n`List` also has kind `*`.\n\nSo what is the kind of `List` itself?\n\n`List` has kind `* -> *`.\n\nThat is, it is a type-level function that accepts a type and returns a type.\n\n## Aside: Higher-Kinded Types in Java\n\nHere we introduce an *encoding* of higher-kinded types for Java.\n\nRecall that interface `Functor` failed because Java insists `F` is a concrete\ntype, not a type constructor. This encoding gives us a way to pretend `F` is\nhigher-kinded.\n\n> Note: I did not invent this encoding. I have seen several projects using it\n> (see the Related Work section). I am not sure where it originated, but it is\n> rather elegant.\n\nConsider:\n\n```\ninterface TApp {}\n\nabstract class TagBase {}\n\nsealed interface Maybe extends TApp {\n record Nothing() implements Maybe {}\n \n record Just(A value) implements Maybe {}\n\n final class Tag extends TagBase {}\n\n static Maybe unwrap(TApp m) {\n return (Maybe) m; // unsafe if we misuse TApp and tag types\n }\n}\n```\n\nLet's unpack this:\n\n- `TApp` represents type application, hence its name.\n - We assume that `F` has kind `* -> *` and `A` has kind `*`.\n - `TApp` represents `F`.\n - Therefore `TApp`, in principle, has kind `*`.\n- `Maybe.Tag` is a sort of proxy type for `Maybe` as an unapplied type\n constructor.\n - `TApp`, in principle, means `Maybe`.\n - That is why `Maybe extends TApp`.\n- `Maybe.Tag` extends `TagBase` just so that we can easily identify this type\n via reflection later.\n\nHow is this useful?\n\nNow we *do* have a mechanism (more of a convention) to represent `Functor`!\n\nCheck it out:\n\n```\ninterface Functor {\n TApp fmap(Function f, TApp fa);\n}\n```\n\nRemember: `TApp` means `F`.\n\nAnd we can also define the witness constructor:\n\n```\nsealed interface Maybe extends TApp {\n // ...\n\n default Maybe map(Function f) { ... }\n\n @TypeClass.Witness\n static Functor functor() {\n return new Functor<>() {\n @Override\n public TApp fmap(Function f, TApp fa) {\n return unwrap(fa).map(f);\n }\n };\n }\n}\n```\n\nLet's unpack that:\n\n- We define a witness constructor for `Functor`.\n - Remember: `Functor` means `Functor`, where `Maybe` is the\n unapplied type constructor.\n- We then have to implement:\n - ` TApp fmap(Function f, TApp fa)`\n - And remember:\n - `TApp` means `Maybe`\n - `TApp` means `Maybe`\n - If we squint our eyes a bit, *it does make sense*.\n- We use `unwrap()` to convert from `TApp` to `Maybe`.\n- `Maybe` is a subtype of `TApp`, so the return type just\n works.\n\nThat's it!\n\nNow, we must extend our type class system to understand these typing\nconventions.\n\n## Subgoal: Extending `ParsedType` to support HKTs\n\nThis is actually not very involved. Check it out:\n\n```\nsealed interface ParsedType {\n // ...\n\n static ParsedType parse(Type java) {\n return switch (java) {\n // New:\n case Class tag\n when parseTagType(tag) instanceof Maybe.Just>(var tagged) ->\n new Const(tagged);\n // New:\n case ParameterizedType p\n when parseAppType(p)\n instanceof Maybe.Just>(Pair(var fun, var arg)) ->\n new App(parse(fun), parse(arg));\n // etc\n };\n }\n\n private static Maybe> parseTagType(Class c) {\n return switch (c.getEnclosingClass()) {\n case Class enclosing when c.getSuperclass().equals(TagBase.class) ->\n Maybe.just(enclosing);\n case null -> Maybe.nothing();\n default -> Maybe.nothing();\n };\n }\n\n private static Maybe> parseAppType(ParameterizedType t) {\n return switch (t.getRawType()) {\n case Class raw when raw.equals(TApp.class) ->\n Maybe.just(Pair.of(t.getActualTypeArguments()[0], t.getActualTypeArguments()[1]));\n default -> Maybe.nothing();\n };\n }\n}\n```\n\nWe only had to add two new pattern-match cases to `parse`:\n\n- `case Class tag when parseTagType(tag) ... tagged`\n - `-> new Const(tagged)`\n - This replaces any occurrence of `T.Tag` with `T` itself.\n- `case ParameterizedType p when parseAppType(p) ... (fun, arg)`\n - `-> new App(parse(fun), parse(arg))`\n - This replaces any occurrence of `TApp` with\n `new App(parse(F), parse(A))`.\n\nThat's it!\n\nI was also surprised! The witness resolution code needs no changes whatsoever!\n\nAlthough, I was worried about potential bugs coming from misuses of `Tag`s and\n`TApp`. So I came up with a lightweight embedded kind-checking mechanism.\n\n## Aside: Kind-checking Java-embedded HKTs\n\nGiven:\n\n```\ninterface Kind {\n sealed interface Base {}\n\n // KStar = *\n final class KStar implements Base {}\n\n // KArr k = * -> k\n final class KArr implements Base {}\n}\n\nabstract class TagBase implements Kind {}\n\n// Full application of a unary type constructor\n// TApp :: (* -> *) -> * -> *\ninterface TApp>, A> extends Kind {}\n\n// Partial application of a binary type constructor\n// TPar :: (* -> * -> *) -> * -> (* -> *)\ninterface TPar>>, A> extends Kind> {}\n```\n\n- `TApp` now can only apply to tags of kind `* -> *`, itself becoming a kind\n `*`.\n- `TPar` applies to tags of kind `* -> * -> *`, itself becoming a kind `* -> *`.\n- This gives us some rudimentary kind-checking in Java\n\nThen:\n\n```\nsealed interface Maybe extends TApp {\n // ...\n\n final class Tag extends TagBase> {}\n\n static Maybe unwrap(TApp value) {\n return (Maybe) value;\n }\n}\n```\n\nAnd also:\n\n```\n@FunctionalInterface\ninterface State extends TApp, A> {\n // ...\n\n @TypeClass.Witness\n static Functor> functor() { ... }\n\n final class Tag extends TagBase>> {}\n\n static State unwrap(TApp, A> value) {\n return (State) value;\n }\n}\n```\n\nNotice in this case that `State` has two type parameters:\n\n- `State.Tag` has kind `KArr>`\n - This means: `* -> * -> *`\n- The first application of `State.Tag` must go through `TPar`.\n- The subsequent application must go through `TApp`.\n\n## Examples: Higher-Kinded Type Clases\n\n### Type Class: Traversable\n\nAccording to Haskell's\n[documentation on Traversable](https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html):\n\n> Traversable is the class of data structures that can be traversed from left to\n> right, performing an action on each element.\n\nThe Haskell type class looks like this:\n\n```\nclass (Functor t, Foldable t) => Traversable t where\n traverse :: Applicative f => (a -> f b) -> t a -> f (t b)\n```\n\nNotice the use of the following features:\n\n- `Traversable` is higher-kinded.\n - Its parameter `t` has kind `* -> *`.\n- `Traversable` has two superclasses: `Functor` and `Foldable`.\n- Its method `traverse` is quantified on three type variables:\n - `a` and `b` are plain types, of kind `*`.\n - `f` is of kind `* -> *`, as it seen applied as `f b` and `f (t b)`.\n- The type variable `f` has the constraint `Applicative f`.\n\n`Traversable` is a rather advanced type class.\n\nLet's translate it into Java.\n\nFor now, let's ignore its superclasses:\n\n```\n@TypeClass\ninterface Traversable>> {\n\n >, A, B>\n TApp> traverse(\n Applicative applicative,\n Function> f,\n TApp t);\n\n // And a static helper, for convenience:\n // (I omitted some types and arguments for brevity)\n static ... traverse(\n Traversable traversable,\n Applicative applicative,\n ...) {\n return traversable.traverse(applicative, f, t);\n }\n}\n```\n\nWe see that:\n\n- `T` has kind `KArr` which means `* -> *`.\n- The method `traverse`:\n - Is generic on three type variables: `F`, `A`, `B`.\n - `F` is also declared as having kind `* -> *`.\n - Depends on a witness of `Applicative`.\n - Declares covariance `TApp` on a couple of places:\n - Because we know that we won't return values of static type `TApp`\n itself, but rather values of type `T`, which in our HKT convention will\n extend `TApp`.\n\nThen:\n\n```\n// Unfortunately for HKTs, we must wrap regular Java lists\nrecord JavaList(List toList) implements TApp {\n // ...\n\n @TypeClass.Witness\n public static Show> show(Show showA) { ... }\n\n @TypeClass.Witness\n public static Functor functor() { ... }\n\n @TypeClass.Witness\n public static Traversable traversable() { ... }\n\n // ...\n}\n\n// and:\n\nsealed interface Maybe {\n // ...\n\n @TypeClass.Witness\n static Applicative applicative() { ... }\n\n // ...\n}\n```\n\nFor example:\n\n```\nTraversable.traverse(\n witness(new Ty<>() {}), // for Traversable\n witness(new Ty<>() {}), // for Applicative\n JavaList.of(1, 2, 3),\n Maybe::just);\n// Returns: Just[value=JavaList[toList=[1, 2, 3]]]\n```\n\n### Type Class: Functor, Applicative, Monad\n\nAs expected:\n\n```\n@TypeClass\ninterface Functor>> {\n TApp map(Function f, TApp fa);\n}\n\n@TypeClass\ninterface Applicative>> extends Functor {\n TApp pure(A a);\n\n TApp ap(TApp> ff, TApp fa);\n\n @Override\n default TApp map(Function f, TApp fa) {\n return ap(pure(f), fa);\n }\n}\n\n@TypeClass\ninterface Monad>> extends Applicative {\n TApp flatMap(Function> f, TApp fa);\n\n @Override\n default TApp map(Function f, TApp fa) {\n return flatMap(a -> pure(f.apply(a)), fa);\n }\n\n @Override\n default TApp ap(TApp> ff, TApp fa) {\n return flatMap(a -> map(f -> f.apply(a), ff), fa);\n }\n}\n```\n\nI currently don't have any interesting `Monad` examples. I may add one or two\nsoon.\n\n## Recap\n\nWe have built:\n\n- A simple mechanism to capture static types for runtime access.\n- An AST and a parser for Java types.\n - Including support for higher-kinded types encoded via 'tag types'.\n- Type unification on said AST of types.\n- A witness resolution algorithm that:\n - For a witness type `C`, finds witness constructors in `C` and `T`.\n - A witness constructor is a public static method annotated with\n `@TypeClass.Witness`.\n - Uses type unification to:\n - Filter relevant witness constructors.\n - Guide the recursive search for witness dependencies.\n\nAnd altogether:\n\n- We are able to resolve arbitrarily nested witnesses for first-order type\n clases like `Eq`, `Ord`, and `Monoid` and also for higher-kinded type classes\n like `Functor`, `Monad`, and `Traversable`.\n- The witness summoning syntax looks like:\n - `C w = witness(new Ty<>() {});`\n- Witness resolution is currently done at runtime. Ideally, we should be able to\n do this work at compile time, as that's where the power of type classes lies\n in languages like Haskell.\n\n## Conclusion\n\nThis was **a lot** of fun to work on. I had never before implemented type\nclasses in a language, and it turned out to be way simpler than I thought. The\nkey insight was figuring out that type unification was all that I needed.\nStupidly, I did not check Haskell's spec to figure that out. But it did come\nsomewhat naturally after a bit of thinking, given my experience in implementing\ntype systems.\n\nThis project was partially inspired by\n[this recent Brian Goetz JVMLS talk](https://www.youtube.com/watch?v=Gz7Or9C0TpM)\nwhere he presents his early ideas on how to bring type clases to Java. His\nproposed syntax is `Show.witness`. And, of course, the mechanism is\nsupposed to resolve witnesses at compile time.\n\nYou can find the complete implementation in\n[this Gist](https://gist.github.com/Garciat/204226a528018fa7d10abb93fa51c4ca).\n\nThe code also contains several other type class examples like QuickCheck's\n[Arbitrary type class](https://hackage-content.haskell.org/package/QuickCheck-2.17.1.0/docs/Test-QuickCheck-Arbitrary.html).\n\n### Future work\n\n- The resolution mechanism could use some caching:\n - For witness constructor lookups.\n - For witness instances themselves.\n- It would be ideal to shift witness resolution to compile time.\n - Perhaps with a javac plugin or something like that?\n\n### Related Work\n\nHere are some related projects and posts:\n\n- [HighJ](https://github.com/DanielGronau/highj)\n\n - HKT encoding via `Higher`.\n - Provides Functor/Monad/etc.\n - **No automatic instance resolution**, instances are explicit classes.\n- [Cyclops React](https://github.com/aol/cyclops)\n\n - Functional programming toolkit for Java.\n - Type class-like interfaces (Functor, Monad, etc.).\n - **Manual instance lookup**, no reflection or unification.\n- [Higher-Kinded-J](https://github.com/higherkindness/higherkinded-j)\n\n - Modern HKT encoding using witness types.\n - Supports Functor, Applicative, Monad, MonadError, etc.\n - **Instances must be explicitly provided**, not inferred.\n- [mduerig/java-functional](https://github.com/mduerig/java-functional)\n\n - Experimental HKT + type class encodings in Java.\n - Conceptually related exploration.\n - **No generic instance search or unification engine**.\n- [Type Classes in Java (blog post)](https://zarinfam.github.io/2018/12/01/type-classes-in-java/)\n\n - Demonstrates type class pattern using interfaces.\n - **Requires manual wiring of instances**.\n- [JavaGI](https://www.infosun.fim.uni-passau.de/cl/staff/sulzmann/javagi/)\n\n - Research extension to Java with Haskell-style type classes.\n - Uses **unification-based instance resolution**.\n - **Requires its own compiler**, not a Java library.\n\n## Annex: Context Instances\n\nConsider this example:\n\n```\nstatic String example(Show showA, A value) {\n return Show.show(witness(new Ty<>() {}), JavaList.of(value));\n}\n```\n\nIt is equivalent to the following Haskell code:\n\n```\nexample :: Show a => a -> String\nexample value = show [value]\n```\n\nIn the Java code, we try to lookup `Show>`, but we don't know what `A`\nis!\n\nSure, at runtime we may know its real type, but we actually would like\nresolution to be static. (Even though we use reflection for witness resolution.)\n\nIn the Haskell code, the available instance of `Show a` as captured by the\nfunction's signature becomes available as a 'context instance' that is used to\nderive `Show [a]` for the call of `show`.\n\nHow can we achieve this in Java?\n\nFirst, we define a type that can capture a witness along with its static type:\n\n```\nabstract class Ctx {\n private final T instance;\n\n Ctx(T instance) {\n this.instance = instance;\n }\n\n public T instance() {\n return instance;\n }\n\n public Type type() {\n return requireNonNull(\n ((ParameterizedType) getClass().getGenericSuperclass())\n .getActualTypeArguments()[0]);\n }\n}\n```\n\nIt leverages the same mechanism as `Ty` to capture static types.\n\nThen, we pass it to the `witness()` method:\n\n```\nstatic String example(Show showA, A value) {\n return Show.show(\n witness(new Ty<>() {}, new Ctx<>(showA) {}),\n JavaList.of(value));\n}\n```\n\nFinally, we update a bit of our type class resolution code:\n\n```\nclass TypeClasses {\n // New: second parameter\n public static T witness(Ty ty, Ctx... context) {\n return switch (summon(ParsedType.parse(ty.type()), parseContext(context))) {\n // ...\n };\n }\n\n // New: parsing Ctx into ContextInstance\n private static List parseContext(Ctx[] context) {\n return Arrays.stream(context)\n .map(ctx -> new ContextInstance(ctx.instance(), ParsedType.parse(ctx.type())))\n .toList();\n }\n\n // ...\n\n // New: second parameter\n private static Either summon(\n ParsedType target, List context) {\n // ...\n }\n\n // New: second parameter\n private static Either> summonAll(\n List targets, List context) {\n // ...\n }\n\n // New: second parameter\n private static List findCandidates(\n ParsedType target, List context) {\n // New: use the context instances along with the discovered witness constructors!\n return Stream.concat(\n context.stream(),\n findRules(target).stream())\n .flatMap(...)\n .toList();\n }\n\n // ...\n\n // New: a new case class for WitnessRule\n private record ContextInstance(Object instance, ParsedType type) implements WitnessRule {\n @Override\n public Maybe> tryMatch(ParsedType target) {\n // This is a concrete instance, so we only check for type equality\n return target.equals(type) ? Maybe.just(List.of()) : Maybe.nothing();\n }\n\n @Override\n public Object instantiate(List dependencies) {\n // Trivial\n return instance;\n }\n }\n}\n```\n\nThat's all. A bit noisy, but rather simple.\n\nNow this works:\n\n```\nstatic String example(Show showA, A value) {\n return Show.show(\n witness(new Ty<>() {}, new Ctx<>(showA) {}),\n JavaList.of(value));\n}\n\nprintln(example(witness(new Ty<>() {}), 123));\n```\n\nHere, the type captured by `new Ctx<>(showA) {}` is `Show`, where `A` is the\n*unique type variable* belonging to the `example` method.\n\nThe `Show>` witness that we are trying to summon needs a `Show` whose\ntype could only possibly exist in this static context!\n\n## Annex: Overlapping Instances\n\nIn Haskell, the `String` type is defined as:\n\n```\ntype String = [Char]\n```\n\nThat is, a `String` is just a list of `Char`.\n\nNow, notice the difference here:\n\n```\nshow [1, 2, 3]\n-- \"[1, 2, 3]\"\n\nshow [('a', 1), ('b', 2)]\n-- \"[('a', 1), ('b', 2)]\"\n\nshow ['a', 'b']\n-- \"\\\"ab\\\"\" what?\n```\n\nThe generic `Show` instance for `[a]` simply intercalates `\", \"` between\nelements.\n\nBut the `Show` instance for `[Char]` behaves differently.\n\nWhy is that? This is due to a language extension called\n[overlapping instances](https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/instances.html#overlapping-instances).\n\nIt allows otherwise ambiguous instances to coexist:\n\n```\ninstance Show a => Show [a] where ...\n\ninstance {-# OVERLAPPING #-} Show [Char] where ...\n```\n\nThe `OVERLAPPING` pragma tells the compiler that this instance may override\nanother instance iff it is more specific.\n\nThe rules for instance specificity are explained in the same link.\n\nNow, consider in Java:\n\n```\nsealed interface FwdList extends TApp {\n record Nil() implements FwdList {}\n\n record Cons(A head, FwdList tail) implements FwdList {}\n\n @TypeClass.Witness\n static Show> show(Show showA) { ... }\n\n // Ambiguous!\n @TypeClass.Witness\n static Show> show() { ... }\n}\n```\n\n`FwdList` (name inspired by\n[C++'s std::forward\\_list](https://en.cppreference.com/w/cpp/container/forward_list.html))\nimplements a data structure like Haskell's lists.\n\nAs it is, witness resolution will fail with an ambiguous witness error.\n\nIn order to support overlapping instance, we must apply some changes.\n\nFirst, let's model Haskell's `OVERLAPPING` and `OVERLAPPABLE` pragmas:\n\n```\n@Retention(RetentionPolicy.RUNTIME)\n@interface TypeClass {\n @Retention(RetentionPolicy.RUNTIME)\n @interface Witness {\n Overlap overlap() default Overlap.NONE;\n\n enum Overlap {\n NONE,\n OVERLAPPING,\n OVERLAPPABLE\n }\n }\n}\n```\n\nThen, we make it accessible from `InstanceConstructor`:\n\n```\nprivate record InstanceConstructor(FuncType func) implements WitnessRule {\n public TypeClass.Witness.Overlap overlap() {\n return func.java().getAnnotation(TypeClass.Witness.class).overlap();\n }\n\n // ...\n}\n```\n\nFinally, we implement the overlapping instances deduction algorithm as described\nin\n[Haskell's spec](https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/instances.html#overlapping-instances):\n\n```\nprivate static List reduceOverlapping(\n List candidates) {\n return candidates.stream()\n .filter(\n iX ->\n candidates.stream()\n .filter(iY -> iX != iY)\n .noneMatch(iY -> isOverlappedBy(iX, iY)))\n .toList();\n}\n\nprivate static boolean isOverlappedBy(\n InstanceConstructor iX, InstanceConstructor iY) {\n return (iX.overlap() == OVERLAPPABLE || iY.overlap() == OVERLAPPING)\n && isSubstitutionInstance(iX, iY)\n && !isSubstitutionInstance(iY, iX);\n}\n\nprivate static boolean isSubstitutionInstance(\n InstanceConstructor base, InstanceConstructor reference) {\n return Unification.unify(base.func().returnType(), reference.func().returnType())\n .fold(() -> false, map -> !map.isEmpty());\n}\n```\n\nAnd we apply it to our candidate resolution function:\n\n```\nprivate static List findCandidates(\n ParsedType target, List context) {\n return Stream.concat(\n context.stream(),\n reduceOverlapping(findRules(target)).stream())\n .flatMap(...)\n .toList();\n}\n```\n\nAnd, of course, we annotate our witness constructor:\n\n```\nsealed interface FwdList extends TApp {\n record Nil() implements FwdList {}\n\n record Cons(A head, FwdList tail) implements FwdList {}\n\n @TypeClass.Witness\n static Show> show(Show showA) { ... }\n\n // OK now!\n @TypeClass.Witness(overlap = OVERLAPPING)\n static Show> show() { ... }\n}\n```\n\nNow, our witness resolution code will pick `Show>` because it\nis more specific AND it declares that it may overlap other instances.\n\n---\n\n*Originally published at [garciat.com](https://garciat.com/posts/java-type-classes/).*\n","body_html":"

Full Haskell-like Type Class resolution in Java

\n

Gabriel Garcia · December 6, 2025

\n

TL;DR

\n

This post explores how far Java’s type system can be pushed by building a small\nHaskell-style type class instance resolution engine entirely in plain Java.

\n

Using only reflection, generic type metadata, and a tiny first-order unifier, we\ncan automatically resolve type class instances (including higher-kinded ones),\nsupport overlapping instances, and derive witnesses for arbitrarily nested\ngeneric types.

\n

It’s not intended for production, but as an experiment it reveals just how much\nstructure Java actually preserves at runtime — and how surprisingly close it can\nget to type-level programming without language changes.

\n

You can also jump straight to the full implemention\nin this gist.

\n

Update: I published a GitHub repo for the project at\ngithub.com/garciat/java-type-classes.

\n

Intro: What are Type Classes?

\n

Consider:

\n
interface Equatable<T> {\n  boolean eq(T other);\n}\n\nrecord Point(int x, int y) implements Equatable<Point> {\n  @Override\n  public boolean eq(Point other) {\n    return x == other.x() && y == other.y();\n  }\n}
\n

That's a pretty simple OOP-style generic interface.

\n

However:

\n
record Dup<A>(A fst, A snd) implements Equatable<Dup<A>> {\n  @Override\n  public boolean eq(Dup<A> other) {\n    return fst.eq(other.fst()) && snd.eq(other.snd());\n    // Error: no method eq() in type A!\n  }\n}
\n

We can't implement eq() for Dup without knowing the fact that\nA extends Equatable<A>.

\n

So let's try that:

\n
record Dup<A extends Equatable<A>>(A fst, A snd) implements Equatable<Dup<A>> {\n  @Override\n  public boolean eq(Dup<A> other) {\n    return fst.eq(other.fst()) && snd.eq(other.snd());\n    // OK\n  }\n}
\n

Now the code compiles.

\n

However, Dup is now only compatible with types that extend Equatable. Dup\nis now less capable.

\n

We could have checked at runtime if each object is instanceof Equatable, but\nthat doesn't work very well with generics. And it may fail at runtime.

\n

Ideally, there would be a way to say:

\n

Dup implements Equatable<Dup<A>> if and only if A implements\nEquatable<A>.

\n

Also, if you think about it, it is a bit strange that the definition of\nequality for a type A depends on the object instance. As in, eq() is an\ninstance method.

\n

It would make more sense if equality depended only on the type A itself.\nRight?

\n

That's where type clases come in:

\n
interface Eq<A> {\n  boolean eq(A x, A y);\n}\n\nrecord Point(int x, int y) {\n  public static Eq<Point> eq() {\n    return (p1, p2) ->\n        p1.x() == p2.x()\n        && p1.y() == p2.y();\n  }\n}\n\nrecord Dup<A>(A fst, A snd) {\n  public static <A> Eq<Dup<A>> eq(Eq<A> eqA) {\n    return (d1, d2) ->\n        eqA.eq(d1.fst(), d2.fst())\n        && eqA.eq(d1.snd(), d2.snd());\n  }\n}
\n

Let's unpack this:

\n
  • Eq<A> now compares two values of type A.

    • This indicates that we are no longer expecting the implicit this parameter

      to be relevant in equality.

  • Point no longer implements the interface.
    • Now it provides a static constructor (factory) for Eq<Point>.
    • We call this a witness that Point conforms to Eq.
  • Dup also does not implement the interface.
    • Its static constructor for Eq<Dup<A>> has a parameter of type Eq<A>.
      • This indicates the dependency that we were looking for:
      • In order to prove Eq<Dup<A>>, we must first prove Eq<A>.

    • It uses the witness Eq<A> eqA, which contains boolean eq(A, A), to

      implement its own intended behavior.

\n

The code is rather simple, but it marks a dramatic change of perspective:

\n

Equality now belongs to the type definition and not to an object instance.

\n

So, what are type classes?

\n

Type classes can be seen as a pattern that allows us to model shared behavior in\na way that puts types first AND is entirely compositional.

\n

Now, in the above example, how do we actually use Dup's eq()?

\n
Eq<Dup<Point>> pointDupEq = Dup.eq(Point.eq());\n\npointDupEq.eq(new Point(1, 1), new Point(1, 1));\n// Returns: true
\n

We must first construct the witness Eq<Dup<Point>> by chaining calls to the\nrespective Eq witness constructors of Dup and Point.

\n

Then, we use this witness to access/invoke the actual logic that we're after.

\n

Notice how this pattern composes very nicely:

\n
static <K, V> Eq<Map<K, V>> mapEq(Eq<K> eqK, Eq<V> eqV) { ... }\n\nstatic <E> Eq<List<E>> listEq(Eq<E> eqE);\n\nstatic Eq<Integer> integerEq();\n\nstatic Eq<String> stringEq();\n\n// then:\n\nEq<Map<String, List<Integer>>> eq =\n  mapEq(stringEq(), listEq(integerEq()));\n\nMap<String, List<Integer>> m1 = ...;\nMap<String, List<Integer>> m2 = ...;\n\neq.eq(m1, m2);
\n

With witness constructors as our building blocks, we can recursively construct\ninfinitely many witnesses, as needed.

\n

A note on nomenclature:

\n

In Haskell, type class 'implementations' are called instances.

\n

Here, I am calling them witnesses because that's how Java's Architect, Brian\nGoetz, decided to refer to them in\na recent talk he gave about\nbringing type classes to Java sometime in the future.

\n

Now, wouldn't it be great if we didn't have to manually construct these\nwitnesses?

\n

Goal: Programmatically instantiating witnesses

\n

Given:

\n
@TypeClass\ninterface Show<A> {\n  String show(A value);\n\n  // Convenience shortcut\n  static <A> String show(Show<A> showA, A value) {\n    return showA.show(value);\n  }\n\n  @TypeClass.Witness\n  static Show<Integer> showInteger() { ... }\n\n  @TypeClass.Witness\n  static <A> Show<List<A>> showList(Show<A> showA) { ... }\n}
\n

Instead of:

\n
Show<List<List<Integer>>> w =\n    Show.showList(Show.showList(Show.showInteger()));\n\nShow.show(w, List.of(List.of(1, 2), List.of(3, 4)));\n// Returns: "[[1, 2], [3, 4]]"
\n

We want:

\n
Show.show(witness(), List.of(List.of(1, 2), List.of(3, 4)));\n// Returns: "[[1, 2], [3, 4]]"
\n

Which means that the witness() method is able to automatically construct the\nrequired witness for Show<List<List<Integer>>>.

\n

How do we get there?

\n

First, we must understand some aspects of how Java generics work at runtime.

\n

Aside: Java Generics and Type Erasure

\n

It is a well-known fact that Java generics get erased at runtime.

\n

However, there are a few scenarios in which generics do get reified!

\n

Note: 'Type Reification' is the process by which type information is made\nconcrete and available at runtime.

\n

Given:

\n
interface Stream<T> { ... }\n\ninterface IntStream extends Stream<Integer> { ... }
\n

Then:

\n
IntStream.class.getInterfaces()[0];\n// Returns: Stream\n\nIntStream.class.getGenericInterfaces()[0];\n// Returns: Stream<Integer>
\n

This means that Java did preserve the generic type arguments for the supertype\nStream<Integer>. (We just need to know where to look for it.)

\n

Note that this also occurs with anonymous classes:

\n
var s = new Stream<String>() { ... };\n\ns.getClass().getGenericInterfaces()[0];\n// Returns: Stream<String>
\n

This leads us to our first workaround:

\n

Aside: Capturing static types

\n

We define:

\n
interface Ty<T> {\n  default Type type() {\n    return requireNonNull(\n        ((ParameterizedType) getClass().getGenericInterfaces()[0])\n            .getActualTypeArguments()[0]);\n  }\n}
\n

Which lets us write:

\n
Type type = new Ty<Map<String, List<Integer>>>() {}.type();\n\nprintln(type);\n// Prints: Map<String, List<Integer>>
\n

Why do we need this?

\n

Because our witness() method will need a runtime representation of the type\nthat it is trying to instantiate.

\n

So our use case has turned into:

\n
Show.show(witness(new Ty<>() {}), List.of(List.of(1, 2), List.of(3, 4)));
\n

Note that we do not have to specify the type argument for Ty<>. Thankfully,\ntype inference does that for us.

\n

Type inference works in this case because the List.of(...) parameter has a\nwell-defined type, and the call to <A> Show.show(Show<A>, A) lets type\ninference flow from the second argument to the first.

\n

Aside: Understanding java.lang.reflect.Type's hierarchy

\n

The standard java.lang.reflect.Type hierarchy consists of:

\n
  • Class<?>
  • GenericArrayType
  • ParameterizedType
  • TypeVariable<?>
  • WildcardType
\n

Where:

\n
  • Class<?>, sometimes referred to as a 'raw type', represents either:
    • A non-generic type like String or Integer.

    • A generic type like Function<T, R> where its type parameter list [T, R]

      can be retrieved via TypeVariable<?>[] getTypeParameters().

  • GenericArrayType represents an array type E[] whose component type E is

    a ParameterizedType or a TypeVariable<?>.

  • ParameterizedType represents a type T<Arg1, Arg2, ..., ArgN>. Its

    getRawType() method returns the class or interface T.

  • TypeVariable<?> represents an unbound type parameter of a generic

    declaration like a generic class/interface or generic method.

  • WildcardType represents an occurrence of ? within a ParameterizedType.
\n

Moreover, a java.lang.reflect.Method can be queried via\nTypeVariable<?>[] getTypeParameters(), Type[] getGenericParameterTypes(),\nand Type getGenericReturnType().

\n

For example:

\n
class Example {\n  static <A> List<A> hello(String s, A[] arr, Optional<?> opt) { ... }\n}
\n

Inspecting the Example's hello method at runtime would yield something like:

\n
Method(\n  name: "hello",\n  typeParameters:\n    [TypeVariable(A)],\n  genericReturnType:\n    ParameterizedType(\n      rawType: List.class,\n      typeArguments: [TypeVariable(A)],\n    ),\n  genericParameterTypes:\n    [\n      String.class,\n      GenericArrayType(componentType: TypeVariable(A)),\n      ParameterizedType(\n        rawType: Optional.class,\n        typeArguments: [WildcardType()]\n      )\n    ]\n)
\n

Note that the three ocurrences of TypeVariable(A) are unique in the sense that\nthey compare equal() to each other, but not to other type variable\ninstances, even if their names are also A.

\n

Subgoal: Parsing java.lang.reflect.Type into an AST

\n

We want to do this for a few reasons:

\n
  • java.lang.reflect.Type is not convenient for programming:
    • It is not a sealed hierarchy, so pattern-matching on it is error-prone.
    • Both Class<?> and GenericArrayType may be array types.

    • Class<?> may represent a primitive type, like int or float, which does

      not participate in generic parameterization (yet).

    • Type application as represented by ParameterizedType is variadic.

      Single-parameter-a-time is easier to program against.

  • When we get to higher-kinded type classes (spoiler!), then we will need our

    own type representation anyway.

\n

Here's the AST:

\n
sealed interface ParsedType {\n  record Var(TypeVariable<?> java) implements ParsedType {}\n\n  record App(ParsedType fun, ParsedType arg) implements ParsedType {}\n\n  record ArrayOf(ParsedType elementType) implements ParsedType {}\n\n  record Const(Class<?> java) implements ParsedType {}\n\n  record Primitive(Class<?> java) implements ParsedType {}\n}
\n

And these are our parsing rules:

\n
sealed interface ParsedType {\n  // ...\n\n  static ParsedType parse(Type java) {\n    return switch (java) {\n      case Class<?> arr when arr.isArray() ->\n          new ArrayOf(parse(arr.getComponentType()));\n      case Class<?> prim when prim.isPrimitive() ->\n          new Primitive(prim);\n      case Class<?> c ->\n          new Const(c);\n      case TypeVariable<?> v ->\n          new Var(v);\n      case ParameterizedType p ->\n          parseAll(p.getActualTypeArguments()).stream()\n              .reduce(parse(p.getRawType()), App::new);\n      case GenericArrayType a ->\n          new ArrayOf(parse(a.getGenericComponentType()));\n      case WildcardType w ->\n          throw new IllegalArgumentException("Cannot parse wildcard type: " + w);\n      default ->\n          throw new IllegalArgumentException("Unsupported type: " + java);\n    };\n  }\n}
\n

Note: the rule for ParameterizedType will take a type like T<A, B> and\nturn it into App(App(Const(T), A), B).

\n

This means that the generic type T is first applied to A and then to B.

\n

For example, Map<Integer, List<String>> becomes:

\n
App(\n  App(Const(Map.class), Const(Integer.class)),\n  App(Const(List.class), Const(String.class))\n)
\n

That's it! Really, it's not much, but the added uniformity will help our code\ndown the line.

\n

Recap

\n

Until this point we have:

\n

  • new Ty<T>() {}: a way to capture a type T from a static context and access

    it at runtime.

  • ParsedType: a uniform representation for Java's java.lang.reflect.Types.
\n

Now, let's move on to the problem of type class instance resolution.

\n

Subgoal: Witness resolution

\n

Let's consider the following scenario:

\n
@TypeClass\ninterface Show<A> {\n  String show(A value);\n\n  // Convenience shortcut\n  static <A> String show(Show<A> showA, A value) {\n    return showA.show(value);\n  }\n\n  @TypeClass.Witness\n  static Show<Integer> showInteger() { ... }\n\n  @TypeClass.Witness\n  static <A> Show<List<A>> showList(Show<A> showA) { ... }\n}\n\nrecord Pair<A, B>(A fst, B snd) {\n  @TypeClass.Witness\n  public static <A, B> Show<Pair<A, B>> show(Show<A> showA, Show<B> showB) { ... }\n}
\n

We observe that, for example, in order to summon a witness for\nShow<List<Pair<Integer, List<Integer>>>, then we must apply several witness\nconstructors recursively.

\n

What is a witness constructor? It is a public static method annotated with\n@TypeClass.Witness.

\n

But first, we must find the witness constructors!

\n

How do we do that? Do we need to do a runtime scan of all loaded classes?

\n

That would be way too complicated.

\n

In order to reduce our search scope, we can define the following convention:

\n

When trying to resolve a witness C<T> for some type class C and a concrete\ntype T, then we only look for witness constructors within the definitions of\nC and T and nowhere else.

\n

For example, when looking for Show<Integer>, then we scan the methods of\nShow and Integer.

\n

Generally, we will prefer to define witness constructors within concrete types\nand not within type classes. However, for a built-in type like Integer, we\nhave no choice and we must define its witness constructors within the relevant\ntype classes, as we have done with static Show<Integer> showInteger().

\n

Now that we are able to find the relevant witness constructors, how do we:

\n
  • know which of them we must invoke,
  • and in which order?
\n

First, we must understand type unification:

\n

Aside: Type Unification

\n

Type unification is the process of finding a substitution that makes two types\nidentical.

\n

For example, given Pair<[A], String> and Pair<Integer, String>, then the\nsubstitution {A -> Integer} would make the first type identical to the second.

\n

Here, I have placed the type A between square brackets to indicate that it\nis a type variable. We only substitute type variables!

\n

Unification may fail when it encounters incompatible types. For example,\nList<Integer> and List<String> cannot be unified because no substitution\nexists that would make them identical.

\n

Conversely, when two types are already identical, unification succeeds with an\nempty substitution {}.

\n

Because types are recursive, the unification algorithm must also be recursive\n(in nature).

\n

Consider:

\n
unify(\n  Map<Pair<String, [T]>, List<[U]>>,\n  Map<Pair<String, Integer>, List<Optional<Boolean>>>\n)\n\n// we are unifying two types of shape:\n// - Map<K1, V1>\n// - Map<K2, V2>\n// the type constructors match on either side (Map)\n// so we recurse to their type arguments:\n// unify(K1, K2) ∪ unify(V1, V2)\n// and so on!\n\n=   unify(Pair<String, [T]>, Pair<String, Integer>)\n  ∪ unify(List<[U]>, List<Optional<Boolean>>)\n\n=   unify(String, String) // first arguments of Pair\n  ∪ unify([T], Integer)   // second arguments of Pair\n  ∪ unify([U], <Optional<Boolean>) // arguments of List\n\n=   {}\n  ∪ {T -> Integer}\n  ∪ {U -> Optional<Boolean>}\n\n= {T -> Integer, U -> Optional<Boolean>}\n\n// Done!
\n

If any unification step fails, then the entire unification fails:

\n
unify(Pair<[T], Integer>, Pair<String, String>)\n\n=   unify([T], String)\n  ∪ unify(Integer, String)\n\n=   {T -> String}\n  ∪ err\n\n= err
\n

Following is a code listing for the concrete type unification algorithm\nunify() for our ParsedType definition, along with a subsitute() method\nthat applies a substitution to a type.

\n

Listing: Type Unification algorithm for ParsedType

\n

Here we use the Maybe type, which is analogous to Java's Optional. It is\nused to indicate that the unify() function may fail with a nothing() (empty)\ncase. This is different from it returning just(Map.of()) (an empty map), which\nsignals success but without any substitutions. In short, based on the examples\nabove, err is nothing() and {} is just(Map.of()).

\n

A key step here is the unification of App. This is the main driver for the\nalgorithm's recursion.

\n

The following helper methods are relevant to this step:

\n
// applies function `f` if both `ma` and `mb` are present\n<A, B, C> Maybe<C> apply(BiFunction<A, B, C> f, Maybe<A> ma, Maybe<B> mb);\n\n// merges two maps\n// it fails at runtime if duplicate keys /with different values/ exist\n<K, V> Map<K, V> merge(Map<K, V> m1, Map<K, V> m2);
\n

Here's the full code:

\n
class Unification {\n  public static Maybe<Map<ParsedType.Var, ParsedType>> unify(ParsedType t1, ParsedType t2) {\n    return switch (Pair.of(t1, t2)) {\n      case Pair<ParsedType, ParsedType>(ParsedType.Var var1, ParsedType.Primitive p) ->\n          Maybe.nothing(); // no primitives in generics\n      case Pair<ParsedType, ParsedType>(ParsedType.Var var1, var t) ->\n          Maybe.just(Map.of(var1, t));\n      case Pair<ParsedType, ParsedType>(ParsedType.Const const1, ParsedType.Const const2)\n          when const1.equals(const2) ->\n          Maybe.just(Map.of());\n      case Pair<ParsedType, ParsedType>(\n              ParsedType.App(var fun1, var arg1),\n              ParsedType.App(var fun2, var arg2)) ->\n          Maybe.apply(Maps::merge, unify(fun1, fun2), unify(arg1, arg2));\n      case Pair<ParsedType, ParsedType>(\n              ParsedType.ArrayOf(var elem1),\n              ParsedType.ArrayOf(var elem2)) ->\n          unify(elem1, elem2);\n      case Pair<ParsedType, ParsedType>(\n              ParsedType.Primitive(var prim1),\n              ParsedType.Primitive(var prim2))\n          when prim1.equals(prim2) ->\n          Maybe.just(Map.of());\n      default ->\n          Maybe.nothing();\n    };\n  }\n\n  public static ParsedType substitute(Map<ParsedType.Var, ParsedType> map, ParsedType type) {\n    return switch (type) {\n      case ParsedType.Var var ->\n          map.getOrDefault(var, var);\n      case ParsedType.App(var fun, var arg) ->\n          new ParsedType.App(substitute(map, fun), substitute(map, arg));\n      case ParsedType.ArrayOf var ->\n          new ParsedType.ArrayOf(substitute(map, var.elementType()));\n      case ParsedType.Primitive p ->\n          p;\n      case ParsedType.Const c ->\n          c;\n    };\n  }\n\n  public static List<ParsedType> substituteAll(\n      Map<ParsedType.Var, ParsedType> map, List<ParsedType> types) {\n    return types.stream().map(t -> substitute(map, t)).toList();\n  }\n}
\n

Extra: A type representation for static methods

\n
record FuncType(Method java, List<ParsedType> paramTypes, ParsedType returnType) {\n  public static FuncType parse(Method method) {\n    if (!Modifier.isStatic(method.getModifiers())) {\n      throw new IllegalArgumentException("Method must be static: " + method);\n    }\n    return new FuncType(\n        method,\n        ParsedType.parseAll(method.getGenericParameterTypes()),\n        ParsedType.parse(method.getGenericReturnType()));\n  }\n}
\n

Subgoal: Witness resolution, part 2

\n

Why is type unification relevant?

\n

Type unification will guide the witness resolution process in two ways:

\n
  • By checking if any given witness constructor is relevant to our witness goal.

  • And if it is relevant, then it will tell us which witness subgoals to

    resolve next.

\n

For example, when resolving Show<List<Integer>>, we check:

\n
  1. Which witness constructors can we find?
\n
  • We scan List:
    • It contains zero witness constructors.
  • We scan Show, and it contains:
    • Show<Integer> showInteger()
    • <A> Show<List<A>> showList(Show<A> showA)
\n
  1. Which witness constructors apply to our goal?
\n
  • Does Show<Integer> showInteger() apply?
    • We try to unify Show<Integer> and Show<List<Integer>>.
    • Unification fails.
    • Skip this constructor ❌
  • Does <A> Show<List<A>> showList(Show<A> showA) apply?
    • We try to unify Show<List<A>> and Show<List<Integer>>.
    • Unification succeeds with the substitution {A -> Integer}.
    • We can use this constructor ✅
    • But this constructor has an argument: Show<A>
    • If we apply the substitution to the argument, we find our next goal:
      • substitute({A -> Integer}, Show<A>) yields Show<Integer>.
    • Add Show<Integer> to our goals.
\n
  1. Recurse until we have no further goals.
\n

That outlines the witness resolution algorithm.

\n

Recap

\n

Until this point we have:

\n

  • new Ty<T>() {}: a way to capture a type T from a static context and access

    it at runtime.

  • ParsedType: a uniform representation for Java's java.lang.reflect.Types.
  • Unification: an algorithm for type unification of ParsedTypes.
  • And a rough sketch for the overall recursive witness resolution algorithm.
\n

Now, let's put it all together!

\n

Subgoal: Witness resolution implementation

\n

Let's start with the witness constructor lookup code:

\n
@Retention(RetentionPolicy.RUNTIME)\n@interface TypeClass {\n  @Retention(RetentionPolicy.RUNTIME)\n  @interface Witness {}\n}\n\nclass TypeClasses {\n  // ...\n\n  private static List<InstanceConstructor> findRules(ParsedType target) {\n    return switch (target) {\n      case ParsedType.App(var fun, var arg) ->\n          Lists.concat(findRules(fun), findRules(arg));\n      case ParsedType.Const(var java) ->\n          rulesOf(java);\n      case ParsedType.Var(var java) ->\n          List.of();\n      case ParsedType.ArrayOf(var elem) ->\n          List.of();\n      case ParsedType.Primitive(var java) ->\n          List.of();\n    };\n  }\n\n  private static List<InstanceConstructor> rulesOf(Class<?> cls) {\n    return Arrays.stream(cls.getDeclaredMethods())\n        .filter(TypeClasses::isWitnessMethod)\n        .map(FuncType::parse)\n        .map(InstanceConstructor::new)\n        .toList();\n  }\n\n  private static boolean isWitnessMethod(Method m) {\n    return m.accessFlags().contains(PUBLIC)\n        && m.accessFlags().contains(STATIC)\n        && m.isAnnotationPresent(TypeClass.Witness.class);\n  }\n\n  private record InstanceConstructor(FuncType func) {}\n\n  // ...\n}
\n

Now, let's move on to how we choose relevant witness constructors and find our\nsubsequent goals:

\n
class TypeClasses {\n  // ...\n\n  private static List<Candidate> findCandidates(ParsedType target) {\n    return findRules(target).stream()\n        .flatMap(\n            rule ->\n                rule\n                    .tryMatch(target)\n                    .map(requirements -> new Candidate(rule, requirements))\n                    .stream())\n        .toList();\n  }\n\n  private record Candidate(WitnessRule rule, List<ParsedType> requirements) {}\n\n  // Spoiler: we will have another subtype of WitnessRule later on (;\n  private sealed interface WitnessRule {\n    Maybe<List<ParsedType>> tryMatch(ParsedType target);\n\n    Object instantiate(List<Object> dependencies);\n  }\n\n  private record InstanceConstructor(FuncType func) implements WitnessRule {\n    @Override\n    public Maybe<List<ParsedType>> tryMatch(ParsedType target) {\n      return Unification.unify(func.returnType(), target)\n          .map(map -> Unification.substituteAll(map, func.paramTypes()));\n    }\n\n    @Override\n    public Object instantiate(List<Object> dependencies) {\n      try {\n        return func.java().invoke(null, dependencies.toArray());\n      } catch (Exception e) {\n        throw new RuntimeException(e);\n      }\n    }\n  }\n\n  // ...\n}
\n

Then, the code that drives the recursive resolution:

\n
class TypeClasses {\n  // ...\n\n  private static Either<SummonError, Object> summon(ParsedType target) {\n    return switch (ZeroOneMore.of(findCandidates(target, context))) {\n      case ZeroOneMore.One<Candidate>(Candidate(var rule, var requirements)) ->\n          summonAll(requirements, context)\n              .map(rule::instantiate)\n              .mapLeft(error -> new SummonError.Nested(target, error));\n      case ZeroOneMore.Zero<Candidate>() ->\n          Either.left(new SummonError.NotFound(target));\n      case ZeroOneMore.More<Candidate>(var candidates) ->\n          Either.left(new SummonError.Ambiguous(target, candidates));\n    };\n  }\n\n  private static Either<SummonError, List<Object>> summonAll(List<ParsedType> targets) {\n    return Either.traverse(targets, TypeClasses::summon);\n  }\n\n  private sealed interface SummonError {\n    record NotFound(ParsedType target) implements SummonError {}\n\n    record Ambiguous(ParsedType target, List<Candidate> candidates) implements SummonError {}\n\n    record Nested(ParsedType target, SummonError cause) implements SummonError {}\n  }\n\n  // ...\n}
\n

And, finally, the public entry point for all of it:

\n
class TypeClasses {\n  public static <T> T witness(Ty<T> ty) {\n    return switch (summon(ParsedType.parse(ty.type()))) {\n      case Either.Left<SummonError, Object>(SummonError error) ->\n          throw new WitnessResolutionException(error);\n      case Either.Right<SummonError, Object>(Object instance) -> {\n        @SuppressWarnings("unchecked")\n        T typedInstance = (T) instance;\n        yield typedInstance;\n      }\n    };\n  }\n\n  public static class WitnessResolutionException extends RuntimeException {\n    private WitnessResolutionException(SummonError error) {\n      super(error.format());\n    }\n  }\n\n  // ...\n}
\n

Surprinsingly, that's it!

\n

You can find a mostly accurate compilation of all of the above code in\nthis Gist.\n(This was the first version of the type class system that I built.)

\n

Now, let's see it in action.

\n

Examples: First-Order Type Classes & Instances

\n

Type Class: Show

\n

Given:

\n
@TypeClass\ninterface Show<A> {\n  String show(A a);\n\n  static <A> String show(Show<A> showA, A a) {\n    return showA.show(a);\n  }\n\n  @TypeClass.Witness\n  static Show<Integer> integerShow() {\n    return i -> Integer.toString(i);\n  }\n\n  @TypeClass.Witness\n  static Show<String> stringShow() {\n    return s -> "\\"" + s + "\\"";\n  }\n\n  @TypeClass.Witness\n  static <A> Show<Optional<A>> optionalShow(Show<A> showA) {\n    return optA -> optA.map(a -> "Some(" + showA.show(a) + ")").orElse("None");\n  }\n\n  @TypeClass.Witness\n  static <A> Show<List<A>> listShow(Show<A> showA) { ... }\n\n  @TypeClass.Witness\n  static <K, V> Show<Map<K, V>> mapShow(Show<K> showK, Show<V> showV) { ... }\n}
\n

Then:

\n
Map<String, List<Optional<Integer>>> m1 =\n    Map.of(\n        "a", List.of(Optional.of(1), Optional.empty()),\n        "b", List.of(Optional.of(2), Optional.of(3)));\n\nprintln(Show.show(witness(new Ty<>() {}), m1));\n// Prints: {"a": [Some(1), None], "b": [Some(2), Some(3)]}
\n

Note that this requires the recursive instantiation of 5 witness constructors.\nHere's what some debug logs show:

\n
Instantiating: () -> Show[A](String)\nInstantiating: () -> Show[A](Integer)\nInstantiating: ∀ A. (Show[A](A)) -> Show[A](Optional[T](A))\nInstantiating: ∀ A. (Show[A](A)) -> Show[A](List[E](A))\nInstantiating: ∀ K V. (Show[A](K), Show[A](V)) -> Show[A](Map[K, V](K)(V))
\n

Type Class: Monoid & Num

\n

Given:

\n
@TypeClass\ninterface Monoid<A> {\n  A combine(A a1, A a2);\n\n  A identity();\n\n  static <A> A combineAll(Monoid<A> monoid, List<A> elements) {\n    A result = monoid.identity();\n    for (A element : elements) {\n      result = monoid.combine(result, element);\n    }\n    return result;\n  }\n}\n\n@TypeClass\ninterface Num<A> {\n  A add(A a1, A a2);\n\n  A mul(A a1, A a2);\n\n  A zero();\n\n  A one();\n\n  @TypeClass.Witness\n  static Num<Integer> integerNum() {\n    return new Num<>() {\n      @Override\n      public Integer add(Integer a1, Integer a2) {\n        return a1 + a2;\n      }\n\n      @Override\n      public Integer mul(Integer a1, Integer a2) {\n        return a1 * a2;\n      }\n\n      @Override\n      public Integer zero() {\n        return 0;\n      }\n\n      @Override\n      public Integer one() {\n        return 1;\n      }\n    };\n  }\n}\n\nrecord Sum<A>(A value) {\n  @TypeClass.Witness\n  public static <A> Monoid<Sum<A>> monoid(Num<A> num) {\n    return new Monoid<>() {\n      @Override\n      public Sum<A> combine(Sum<A> s1, Sum<A> s2) {\n        return new Sum<>(num.add(s1.value(), s2.value()));\n      }\n\n      @Override\n      public Sum<A> identity() {\n        return new Sum<>(num.zero());\n      }\n    };\n  }\n}
\n

Then:

\n
var sums = List.of(new Sum<>(3), new Sum<>(5), new Sum<>(10));\n\nprintln(Monoid.combineAll(witness(new Ty<>() {}), sums));\n// Prints: Sum[value=18]
\n

Type Class: PrintAll

\n

This example is based on:\nhttps://wiki.haskell.org/Varargs

\n

It abuses type classes in order to implement variadic functions. Please read the\nlink above to understand how this works.

\n

It's really striking how it just works with our system!

\n

Given:

\n
@TypeClass\ninterface PrintAll<T> {\n  T printAll(List<String> strings);\n\n  static <T> T of(PrintAll<T> printAll) {\n    return printAll.printAll(List.of());\n  }\n\n  @TypeClass.Witness\n  static PrintAll<Void> base() {\n    return strings -> {\n      for (String s : strings) {\n        System.out.println(s);\n      }\n      return null;\n    };\n  }\n\n  @TypeClass.Witness\n  static <A, R> PrintAll<Function<A, R>> func(Show<A> showA, PrintAll<R> printR) {\n    return strings -> a -> printR.printAll(Lists.concat(strings, List.of(showA.show(a))));\n  }\n}
\n

Then:

\n
Function<String, Function<List<String>, Function<Integer, Void>>> printer =\n    PrintAll.of(witness(new Ty<>() {}));\n\nprinter.apply("Items:").apply(JavaList.of("apple", "banana", "cherry")).apply(42);\n// Prints:\n// "Items:"\n// ["apple", "banana", "cherry"]\n// 42
\n

Type Class: Type Equality!

\n

This examples shows how we can encode propositions about types themselves and\nhave the resolver construct evidence for them.

\n

Reified type equality is very neat construct that I'd like to write more about\nsoon.

\n

For now, let's appreciate how this neatly encodes\nHaskell's own type equality\nin Java.

\n

Consider:

\n
@TypeClass\nsealed interface TyEq<A, B> {\n  A castR(B b);\n\n  B castL(A a);\n\n  @TypeClass.Witness\n  static <T> TyEq<T, T> refl() {\n    return new Refl<>();\n  }\n\n  record Refl<T>() implements TyEq<T, T> {\n\n    @Override\n    public T castR(T t) {\n      return t;\n    }\n\n    @Override\n    public T castL(T t) {\n      return t;\n    }\n  }\n}
\n

TyEq<A, B> represents the proposition that A = B.

\n

And the only possible constructor for it is refl(), which can only prove that\nTyEq<T, T> for any T.

\n

How is that useful?

\n

TyEq<T, T> may be trivial in the static context where it is constructed. But\nit certainly is not in the context where it may be needed.

\n

Take a look:

\n
class List<T> {\n  // ...\n\n  int sum(TyEq<T, Integer> ty) {\n    int s = 0;\n    for (T item : this) {\n      s += ty.castL(item); // casts T to Integer !\n    }\n    return s;\n  }\n\n  // ...\n}\n\n// then\n\nvar xs = List.of(1, 2, 3);\n\nxs.sum(refl());\n// Returns: 6
\n

Within List<T>, we have no idea what T. Code can make no assumptions about\nit. However, if we have a proof that T = Integer, then we can sum the\nelements up into an int.

\n

Now, we can also request them as witnesses in a witness constructor:

\n
@TypeClass\ninterface SumAllInt<A> {\n  A sum(List<Integer> list);\n\n  static <T> T of(SumAllInt<T> sumAllInt) {\n    return sumAllInt.sum(List.of());\n  }\n\n  @TypeClass.Witness\n  static SumAllInt<Integer> base() {\n    return list -> list.stream().mapToInt(Integer::intValue).sum();\n  }\n\n  @TypeClass.Witness\n  static <A, R> SumAllInt<Function<A, R>> func(TyEq<A, Integer> eq, SumAllInt<R> sumR) {\n    return list -> a -> sumR.sum(Lists.concat(list, List.of(eq.castL(a))));\n  }\n}
\n

Similar to the PrintAll example, this lets us summon variadic functions:

\n
Function<Integer, Function<Integer, Function<Integer, Integer>>> sum =\n    SumAllInt.of(witness(new Ty<>() {}));\nprintln(sum.apply(1).apply(2).apply(3));
\n

However, notice how in the func rule, we requested TyEq<A, Integer>. This\nconstrains the A type argument to just Integer.

\n

Funny enough, this is actually only necessary in Haskell due to how integer\nliterals are overloaded. So I implemented this here for no gain. But it was cool\nthat it just worked!

\n

Goal: Higher-Order Type Classes

\n

Consider the Functor type class in Haskell:

\n
class Functor f where\n  fmap :: (a -> b) -> f a - > f b
\n

Notice how f is not a type?

\n

It is not one because it is being applied to types a and b, respectively.

\n

This means that f is a type constructor.

\n

A type constructor is a sort of type-level function that builds new types\nfrom existing types.

\n

Here, we mean function in the sense that it has the mathematical property of\nbeing injective. That is, no two inputs map to the same output.

\n

In practice, this means that if we know that the output is the same, then the\ninput must be the same:

\n

F<X> = F<Y> ⇒ X = Y

\n

This property is what allows us to unify under type constructors.

\n

In Java, class List<T> can be seen as a type constructor. Though we don't use\ntype application syntax as in Haskell, we do use type parameterization syntax:\nList<Integer>. In Java, generic types cannot be partially applied. That is,\nfor a type class C<T1, T2, ..., TN>, we must provide all N type arguments at\nonce.

\n

Let's try representing the Functor type class with a Java interface:

\n
interface Functor<F> {\n  <A, B> F<B> fmap(Function<A, B> f, F<A> fa);\n}
\n

Uh-oh:

\n
The type F is not generic; it cannot be parameterized with arguments <B>
\n

Indeed, Java requires that the type parameter F is a type, and not a type\nconstructor.

\n

Are we cooked?

\n

Not quite.

\n

Aside: What is a kind?

\n

Simply: values have types; types have kinds.

\n

42 has type Integer.

\n

Integer has kind * (read: star).

\n

The syntax * for the kind of plain types comes from Haskell.

\n

We could also say Integer has kind Type, but that may be confusing given\nhow overloaded the word 'type' is in this context.

\n

List<Integer> also has kind *.

\n

So what is the kind of List itself?

\n

List has kind * -> *.

\n

That is, it is a type-level function that accepts a type and returns a type.

\n

Aside: Higher-Kinded Types in Java

\n

Here we introduce an encoding of higher-kinded types for Java.

\n

Recall that interface Functor<F> failed because Java insists F is a concrete\ntype, not a type constructor. This encoding gives us a way to pretend F is\nhigher-kinded.

\n

Note: I did not invent this encoding. I have seen several projects using it\n(see the Related Work section). I am not sure where it originated, but it is\nrather elegant.

\n

Consider:

\n
interface TApp<F, A> {}\n\nabstract class TagBase {}\n\nsealed interface Maybe<A> extends TApp<Maybe.Tag, A> {\n  record Nothing<A>() implements Maybe<A> {}\n  \n  record Just<A>(A value) implements Maybe<A> {}\n\n  final class Tag extends TagBase {}\n\n  static <A> Maybe<A> unwrap(TApp<Maybe.Tag, A> m) {\n    return (Maybe<A>) m; // unsafe if we misuse TApp and tag types\n  }\n}
\n

Let's unpack this:

\n
  • TApp<F, A> represents type application, hence its name.
    • We assume that F has kind * -> * and A has kind *.
    • TApp<F, A> represents F<A>.
    • Therefore TApp<F, A>, in principle, has kind *.

  • Maybe.Tag is a sort of proxy type for Maybe as an unapplied type

    constructor.

    \n
    • TApp<Maybe.Tag, A>, in principle, means Maybe<A>.
    • That is why Maybe<A> extends TApp<Maybe.Tag, A>.

  • Maybe.Tag extends TagBase just so that we can easily identify this type

    via reflection later.

\n

How is this useful?

\n

Now we do have a mechanism (more of a convention) to represent Functor!

\n

Check it out:

\n
interface Functor<F> {\n  <A, B> TApp<F, B> fmap(Function<A, B> f, TApp<F, A> fa);\n}
\n

Remember: TApp<F, A> means F<A>.

\n

And we can also define the witness constructor:

\n
sealed interface Maybe<A> extends TApp<Maybe.Tag, A> {\n  // ...\n\n  default <B> Maybe<B> map(Function<A, B> f) { ... }\n\n  @TypeClass.Witness\n  static Functor<Maybe.Tag> functor() {\n    return new Functor<>() {\n      @Override\n      public <A, B> TApp<Maybe.Tag, B> fmap(Function<A, B> f, TApp<Maybe.Tag, A> fa) {\n        return unwrap(fa).map(f);\n      }\n    };\n  }\n}
\n

Let's unpack that:

\n
  • We define a witness constructor for Functor<Maybe.Tag>.

    • Remember: Functor<Maybe.Tag> means Functor<Maybe>, where Maybe is the

      unapplied type constructor.

  • We then have to implement:
    • <A, B> TApp<Maybe.Tag, B> fmap(Function<A, B> f, TApp<Maybe.Tag, A> fa)
    • And remember:
      • TApp<Maybe.Tag, A> means Maybe<A>
      • TApp<Maybe.Tag, B> means Maybe<B>
    • If we squint our eyes a bit, it does make sense.
  • We use unwrap() to convert from TApp<Maybe.Tag, A> to Maybe<A>.

  • Maybe<B> is a subtype of TApp<Maybe.Tag, B>, so the return type just

    works.

\n

That's it!

\n

Now, we must extend our type class system to understand these typing\nconventions.

\n

Subgoal: Extending ParsedType to support HKTs

\n

This is actually not very involved. Check it out:

\n
sealed interface ParsedType {\n  // ...\n\n  static ParsedType parse(Type java) {\n    return switch (java) {\n      // New:\n      case Class<?> tag\n        when parseTagType(tag) instanceof Maybe.Just<Class<?>>(var tagged) ->\n          new Const(tagged);\n      // New:\n      case ParameterizedType p\n          when parseAppType(p)\n              instanceof Maybe.Just<Pair<Type, Type>>(Pair<Type, Type>(var fun, var arg)) ->\n          new App(parse(fun), parse(arg));\n      // etc\n    };\n  }\n\n  private static Maybe<Class<?>> parseTagType(Class<?> c) {\n    return switch (c.getEnclosingClass()) {\n      case Class<?> enclosing when c.getSuperclass().equals(TagBase.class) ->\n          Maybe.just(enclosing);\n      case null -> Maybe.nothing();\n      default -> Maybe.nothing();\n    };\n  }\n\n  private static Maybe<Pair<Type, Type>> parseAppType(ParameterizedType t) {\n    return switch (t.getRawType()) {\n      case Class<?> raw when raw.equals(TApp.class) ->\n          Maybe.just(Pair.of(t.getActualTypeArguments()[0], t.getActualTypeArguments()[1]));\n      default -> Maybe.nothing();\n    };\n  }\n}
\n

We only had to add two new pattern-match cases to parse:

\n
  • case Class<?> tag when parseTagType(tag) ... tagged
    • -> new Const(tagged)
    • This replaces any occurrence of T.Tag with T itself.
  • case ParameterizedType p when parseAppType(p) ... (fun, arg)
    • -> new App(parse(fun), parse(arg))

    • This replaces any occurrence of TApp<F, A> with

      new App(parse(F), parse(A)).

\n

That's it!

\n

I was also surprised! The witness resolution code needs no changes whatsoever!

\n

Although, I was worried about potential bugs coming from misuses of Tags and\nTApp. So I came up with a lightweight embedded kind-checking mechanism.

\n

Aside: Kind-checking Java-embedded HKTs

\n

Given:

\n
interface Kind<K extends Kind.Base> {\n  sealed interface Base {}\n\n  // KStar = *\n  final class KStar implements Base {}\n\n  // KArr k = * -> k\n  final class KArr<K extends Base> implements Base {}\n}\n\nabstract class TagBase<K extends Kind.Base> implements Kind<K> {}\n\n// Full application of a unary type constructor\n// TApp :: (* -> *) -> * -> *\ninterface TApp<Tag extends Kind<KArr<KStar>>, A> extends Kind<KStar> {}\n\n// Partial application of a binary type constructor\n// TPar :: (* -> * -> *) -> * -> (* -> *)\ninterface TPar<Tag extends Kind<KArr<KArr<KStar>>>, A> extends Kind<KArr<KStar>> {}
\n

  • TApp now can only apply to tags of kind * -> *, itself becoming a kind

    *.

  • TPar applies to tags of kind * -> * -> *, itself becoming a kind * -> *.
  • This gives us some rudimentary kind-checking in Java
\n

Then:

\n
sealed interface Maybe<A> extends TApp<Maybe.Tag, A> {\n  // ...\n\n  final class Tag extends TagBase<KArr<KStar>> {}\n\n  static <A> Maybe<A> unwrap(TApp<Tag, A> value) {\n    return (Maybe<A>) value;\n  }\n}
\n

And also:

\n
@FunctionalInterface\ninterface State<S, A> extends TApp<TPar<State.Tag, S>, A> {\n  // ...\n\n  @TypeClass.Witness\n  static <S> Functor<TPar<Tag, S>> functor() { ... }\n\n  final class Tag extends TagBase<KArr<KArr<KStar>>> {}\n\n  static <S, A> State<S, A> unwrap(TApp<TPar<Tag, S>, A> value) {\n    return (State<S, A>) value;\n  }\n}
\n

Notice in this case that State has two type parameters:

\n
  • State.Tag has kind KArr<KArr<KStar>>
    • This means: * -> * -> *
  • The first application of State.Tag must go through TPar.
  • The subsequent application must go through TApp.
\n

Examples: Higher-Kinded Type Clases

\n

Type Class: Traversable

\n

According to Haskell's\ndocumentation on Traversable:

\n

Traversable is the class of data structures that can be traversed from left to\nright, performing an action on each element.

\n

The Haskell type class looks like this:

\n
class (Functor t, Foldable t) => Traversable t where\n  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
\n

Notice the use of the following features:

\n
  • Traversable is higher-kinded.
    • Its parameter t has kind * -> *.
  • Traversable has two superclasses: Functor and Foldable.
  • Its method traverse is quantified on three type variables:
    • a and b are plain types, of kind *.
    • f is of kind * -> *, as it seen applied as f b and f (t b).
  • The type variable f has the constraint Applicative f.
\n

Traversable is a rather advanced type class.

\n

Let's translate it into Java.

\n

For now, let's ignore its superclasses:

\n
@TypeClass\ninterface Traversable<T extends Kind<KArr<KStar>>> {\n\n  <F extends Kind<KArr<KStar>>, A, B>\n      TApp<F, ? extends TApp<T, B>> traverse(\n          Applicative<F> applicative,\n          Function<A, ? extends TApp<F, B>> f,\n          TApp<T, A> t);\n\n  // And a static helper, for convenience:\n  // (I omitted some types and arguments for brevity)\n  static <F, A, B> ... traverse(\n      Traversable<T> traversable,\n      Applicative<F> applicative,\n      ...) {\n    return traversable.traverse(applicative, f, t);\n  }\n}
\n

We see that:

\n
  • T has kind KArr<KStar> which means * -> *.
  • The method traverse:
    • Is generic on three type variables: F, A, B.
      • F is also declared as having kind * -> *.
    • Depends on a witness of Applicative<F>.
    • Declares covariance TApp<T, B> on a couple of places:

      • Because we know that we won't return values of static type TApp<T, B>

        itself, but rather values of type T<B>, which in our HKT convention will\nextend TApp<T, B>.

\n

Then:

\n
// Unfortunately for HKTs, we must wrap regular Java lists\nrecord JavaList<A>(List<A> toList) implements TApp<JavaList.Tag, A> {\n  // ...\n\n  @TypeClass.Witness\n  public static <A> Show<JavaList<A>> show(Show<A> showA) { ... }\n\n  @TypeClass.Witness\n  public static Functor<JavaList.Tag> functor() { ... }\n\n  @TypeClass.Witness\n  public static Traversable<JavaList.Tag> traversable() { ... }\n\n  // ...\n}\n\n// and:\n\nsealed interface Maybe<A> {\n  // ...\n\n  @TypeClass.Witness\n  static Applicative<Maybe.Tag> applicative() { ... }\n\n  // ...\n}
\n

For example:

\n
Traversable.traverse(\n    witness(new Ty<>() {}), // for Traversable<JavaList>\n    witness(new Ty<>() {}), // for Applicative<Maybe>\n    JavaList.of(1, 2, 3),\n    Maybe::just);\n// Returns: Just[value=JavaList[toList=[1, 2, 3]]]
\n

Type Class: Functor, Applicative, Monad

\n

As expected:

\n
@TypeClass\ninterface Functor<F extends Kind<KArr<KStar>>> {\n  <A, B> TApp<F, B> map(Function<A, B> f, TApp<F, A> fa);\n}\n\n@TypeClass\ninterface Applicative<F extends Kind<KArr<KStar>>> extends Functor<F> {\n  <A> TApp<F, A> pure(A a);\n\n  <A, B> TApp<F, B> ap(TApp<F, Function<A, B>> ff, TApp<F, A> fa);\n\n  @Override\n  default <A, B> TApp<F, B> map(Function<A, B> f, TApp<F, A> fa) {\n    return ap(pure(f), fa);\n  }\n}\n\n@TypeClass\ninterface Monad<M extends Kind<KArr<KStar>>> extends Applicative<M> {\n  <A, B> TApp<M, B> flatMap(Function<A, TApp<M, B>> f, TApp<M, A> fa);\n\n  @Override\n  default <A, B> TApp<M, B> map(Function<A, B> f, TApp<M, A> fa) {\n    return flatMap(a -> pure(f.apply(a)), fa);\n  }\n\n  @Override\n  default <A, B> TApp<M, B> ap(TApp<M, Function<A, B>> ff, TApp<M, A> fa) {\n    return flatMap(a -> map(f -> f.apply(a), ff), fa);\n  }\n}
\n

I currently don't have any interesting Monad examples. I may add one or two\nsoon.

\n

Recap

\n

We have built:

\n
  • A simple mechanism to capture static types for runtime access.
  • An AST and a parser for Java types.
    • Including support for higher-kinded types encoded via 'tag types'.
  • Type unification on said AST of types.
  • A witness resolution algorithm that:
    • For a witness type C<T>, finds witness constructors in C and T.

      • A witness constructor is a public static method annotated with

        @TypeClass.Witness.

    • Uses type unification to:
      • Filter relevant witness constructors.
      • Guide the recursive search for witness dependencies.
\n

And altogether:

\n

  • We are able to resolve arbitrarily nested witnesses for first-order type

    clases like Eq, Ord, and Monoid and also for higher-kinded type classes\nlike Functor, Monad, and Traversable.

  • The witness summoning syntax looks like:
    • C<T> w = witness(new Ty<>() {});

  • Witness resolution is currently done at runtime. Ideally, we should be able to

    do this work at compile time, as that's where the power of type classes lies\nin languages like Haskell.

\n

Conclusion

\n

This was a lot of fun to work on. I had never before implemented type\nclasses in a language, and it turned out to be way simpler than I thought. The\nkey insight was figuring out that type unification was all that I needed.\nStupidly, I did not check Haskell's spec to figure that out. But it did come\nsomewhat naturally after a bit of thinking, given my experience in implementing\ntype systems.

\n

This project was partially inspired by\nthis recent Brian Goetz JVMLS talk\nwhere he presents his early ideas on how to bring type clases to Java. His\nproposed syntax is Show<Integer>.witness. And, of course, the mechanism is\nsupposed to resolve witnesses at compile time.

\n

You can find the complete implementation in\nthis Gist.

\n

The code also contains several other type class examples like QuickCheck's\nArbitrary type class.

\n

Future work

\n
  • The resolution mechanism could use some caching:
    • For witness constructor lookups.
    • For witness instances themselves.
  • It would be ideal to shift witness resolution to compile time.
    • Perhaps with a javac plugin or something like that?
\n

Related Work

\n

Here are some related projects and posts:

\n
  • HighJ
    • HKT encoding via Higher<F, A>.
    • Provides Functor/Monad/etc.
    • No automatic instance resolution, instances are explicit classes.
  • Cyclops React
    • Functional programming toolkit for Java.
    • Type class-like interfaces (Functor, Monad, etc.).
    • Manual instance lookup, no reflection or unification.
  • Higher-Kinded-J
    • Modern HKT encoding using witness types.
    • Supports Functor, Applicative, Monad, MonadError, etc.
    • Instances must be explicitly provided, not inferred.
  • mduerig/java-functional
    • Experimental HKT + type class encodings in Java.
    • Conceptually related exploration.
    • No generic instance search or unification engine.
  • Type Classes in Java (blog post)
    • Demonstrates type class pattern using interfaces.
    • Requires manual wiring of instances.
  • JavaGI
    • Research extension to Java with Haskell-style type classes.
    • Uses unification-based instance resolution.
    • Requires its own compiler, not a Java library.
\n

Annex: Context Instances

\n

Consider this example:

\n
static <A> String example(Show<A> showA, A value) {\n  return Show.show(witness(new Ty<>() {}), JavaList.of(value));\n}
\n

It is equivalent to the following Haskell code:

\n
example :: Show a => a -> String\nexample value = show [value]
\n

In the Java code, we try to lookup Show<List<A>>, but we don't know what A\nis!

\n

Sure, at runtime we may know its real type, but we actually would like\nresolution to be static. (Even though we use reflection for witness resolution.)

\n

In the Haskell code, the available instance of Show a as captured by the\nfunction's signature becomes available as a 'context instance' that is used to\nderive Show [a] for the call of show.

\n

How can we achieve this in Java?

\n

First, we define a type that can capture a witness along with its static type:

\n
abstract class Ctx<T> {\n  private final T instance;\n\n  Ctx(T instance) {\n    this.instance = instance;\n  }\n\n  public T instance() {\n    return instance;\n  }\n\n  public Type type() {\n    return requireNonNull(\n        ((ParameterizedType) getClass().getGenericSuperclass())\n            .getActualTypeArguments()[0]);\n  }\n}
\n

It leverages the same mechanism as Ty<T> to capture static types.

\n

Then, we pass it to the witness() method:

\n
static <A> String example(Show<A> showA, A value) {\n  return Show.show(\n      witness(new Ty<>() {}, new Ctx<>(showA) {}),\n      JavaList.of(value));\n}
\n

Finally, we update a bit of our type class resolution code:

\n
class TypeClasses {\n  // New: second parameter\n  public static <T> T witness(Ty<T> ty, Ctx<?>... context) {\n    return switch (summon(ParsedType.parse(ty.type()), parseContext(context))) {\n      // ...\n    };\n  }\n\n  // New: parsing Ctx<?> into ContextInstance\n  private static List<ContextInstance> parseContext(Ctx<?>[] context) {\n    return Arrays.stream(context)\n        .map(ctx -> new ContextInstance(ctx.instance(), ParsedType.parse(ctx.type())))\n        .toList();\n  }\n\n  // ...\n\n  // New: second parameter\n  private static Either<SummonError, Object> summon(\n      ParsedType target, List<ContextInstance> context) {\n    // ...\n  }\n\n  // New: second parameter\n  private static Either<SummonError, List<Object>> summonAll(\n      List<ParsedType> targets, List<ContextInstance> context) {\n    // ...\n  }\n\n  // New: second parameter\n  private static List<Candidate> findCandidates(\n      ParsedType target, List<ContextInstance> context) {\n    // New: use the context instances along with the discovered witness constructors!\n    return Stream.<WitnessRule>concat(\n            context.stream(),\n            findRules(target).stream())\n        .flatMap(...)\n        .toList();\n  }\n\n  // ...\n\n  // New: a new case class for WitnessRule\n  private record ContextInstance(Object instance, ParsedType type) implements WitnessRule {\n    @Override\n    public Maybe<List<ParsedType>> tryMatch(ParsedType target) {\n      // This is a concrete instance, so we only check for type equality\n      return target.equals(type) ? Maybe.just(List.of()) : Maybe.nothing();\n    }\n\n    @Override\n    public Object instantiate(List<Object> dependencies) {\n      // Trivial\n      return instance;\n    }\n  }\n}
\n

That's all. A bit noisy, but rather simple.

\n

Now this works:

\n
static <A> String example(Show<A> showA, A value) {\n  return Show.show(\n      witness(new Ty<>() {}, new Ctx<>(showA) {}),\n      JavaList.of(value));\n}\n\nprintln(example(witness(new Ty<>() {}), 123));
\n

Here, the type captured by new Ctx<>(showA) {} is Show<A>, where A is the\nunique type variable belonging to the example method.

\n

The Show<List<A>> witness that we are trying to summon needs a Show<A> whose\ntype could only possibly exist in this static context!

\n

Annex: Overlapping Instances

\n

In Haskell, the String type is defined as:

\n
type String = [Char]
\n

That is, a String is just a list of Char.

\n

Now, notice the difference here:

\n
show [1, 2, 3]\n-- "[1, 2, 3]"\n\nshow [('a', 1), ('b', 2)]\n-- "[('a', 1), ('b', 2)]"\n\nshow ['a', 'b']\n-- "\\"ab\\"" what?
\n

The generic Show instance for [a] simply intercalates ", " between\nelements.

\n

But the Show instance for [Char] behaves differently.

\n

Why is that? This is due to a language extension called\noverlapping instances.

\n

It allows otherwise ambiguous instances to coexist:

\n
instance Show a => Show [a] where ...\n\ninstance {-# OVERLAPPING #-} Show [Char] where ...
\n

The OVERLAPPING pragma tells the compiler that this instance may override\nanother instance iff it is more specific.

\n

The rules for instance specificity are explained in the same link.

\n

Now, consider in Java:

\n
sealed interface FwdList<A> extends TApp<FwdList.Tag, A> {\n  record Nil<A>() implements FwdList<A> {}\n\n  record Cons<A>(A head, FwdList<A> tail) implements FwdList<A> {}\n\n  @TypeClass.Witness\n  static <A> Show<FwdList<A>> show(Show<A> showA) { ... }\n\n  // Ambiguous!\n  @TypeClass.Witness\n  static Show<FwdList<Character>> show() { ... }\n}
\n

FwdList (name inspired by\nC++'s std::forward_list)\nimplements a data structure like Haskell's lists.

\n

As it is, witness resolution will fail with an ambiguous witness error.

\n

In order to support overlapping instance, we must apply some changes.

\n

First, let's model Haskell's OVERLAPPING and OVERLAPPABLE pragmas:

\n
@Retention(RetentionPolicy.RUNTIME)\n@interface TypeClass {\n  @Retention(RetentionPolicy.RUNTIME)\n  @interface Witness {\n    Overlap overlap() default Overlap.NONE;\n\n    enum Overlap {\n      NONE,\n      OVERLAPPING,\n      OVERLAPPABLE\n    }\n  }\n}
\n

Then, we make it accessible from InstanceConstructor:

\n
private record InstanceConstructor(FuncType func) implements WitnessRule {\n  public TypeClass.Witness.Overlap overlap() {\n    return func.java().getAnnotation(TypeClass.Witness.class).overlap();\n  }\n\n  // ...\n}
\n

Finally, we implement the overlapping instances deduction algorithm as described\nin\nHaskell's spec:

\n
private static List<InstanceConstructor> reduceOverlapping(\n    List<InstanceConstructor> candidates) {\n  return candidates.stream()\n      .filter(\n          iX ->\n              candidates.stream()\n                  .filter(iY -> iX != iY)\n                  .noneMatch(iY -> isOverlappedBy(iX, iY)))\n      .toList();\n}\n\nprivate static boolean isOverlappedBy(\n    InstanceConstructor iX, InstanceConstructor iY) {\n  return (iX.overlap() == OVERLAPPABLE || iY.overlap() == OVERLAPPING)\n      && isSubstitutionInstance(iX, iY)\n      && !isSubstitutionInstance(iY, iX);\n}\n\nprivate static boolean isSubstitutionInstance(\n    InstanceConstructor base, InstanceConstructor reference) {\n  return Unification.unify(base.func().returnType(), reference.func().returnType())\n      .fold(() -> false, map -> !map.isEmpty());\n}
\n

And we apply it to our candidate resolution function:

\n
private static List<Candidate> findCandidates(\n    ParsedType target, List<ContextInstance> context) {\n  return Stream.<WitnessRule>concat(\n          context.stream(),\n          reduceOverlapping(findRules(target)).stream())\n      .flatMap(...)\n      .toList();\n}
\n

And, of course, we annotate our witness constructor:

\n
sealed interface FwdList<A> extends TApp<FwdList.Tag, A> {\n  record Nil<A>() implements FwdList<A> {}\n\n  record Cons<A>(A head, FwdList<A> tail) implements FwdList<A> {}\n\n  @TypeClass.Witness\n  static <A> Show<FwdList<A>> show(Show<A> showA) { ... }\n\n  // OK now!\n  @TypeClass.Witness(overlap = OVERLAPPING)\n  static Show<FwdList<Character>> show() { ... }\n}
\n

Now, our witness resolution code will pick Show<FwdList<Character>> because it\nis more specific AND it declares that it may overlap other instances.

\n
\n

Originally published at garciat.com.

","headings":[{"level":1,"text":"Full Haskell-like Type Class resolution in Java","id":"full-haskell-like-type-class-resolution-in-java"},{"level":2,"text":"TL;DR","id":"tl-dr"},{"level":2,"text":"Intro: What are Type Classes?","id":"intro-what-are-type-classes"},{"level":2,"text":"Goal: Programmatically instantiating witnesses","id":"goal-programmatically-instantiating-witnesses"},{"level":2,"text":"Aside: Java Generics and Type Erasure","id":"aside-java-generics-and-type-erasure"},{"level":2,"text":"Aside: Capturing static types","id":"aside-capturing-static-types"},{"level":2,"text":"Aside: Understanding java.lang.reflect.Type's hierarchy","id":"aside-understanding-java-lang-reflect-type-s-hierarchy"},{"level":2,"text":"Subgoal: Parsing java.lang.reflect.Type into an AST","id":"subgoal-parsing-java-lang-reflect-type-into-an-ast"},{"level":2,"text":"Recap","id":"recap"},{"level":2,"text":"Subgoal: Witness resolution","id":"subgoal-witness-resolution"},{"level":2,"text":"Aside: Type Unification","id":"aside-type-unification"},{"level":3,"text":"Listing: Type Unification algorithm for ParsedType","id":"listing-type-unification-algorithm-for-parsedtype"},{"level":3,"text":"Extra: A type representation for static methods","id":"extra-a-type-representation-for-static-methods"},{"level":2,"text":"Subgoal: Witness resolution, part 2","id":"subgoal-witness-resolution-part-2"},{"level":2,"text":"Recap","id":"recap-2"},{"level":2,"text":"Subgoal: Witness resolution implementation","id":"subgoal-witness-resolution-implementation"},{"level":2,"text":"Examples: First-Order Type Classes & Instances","id":"examples-first-order-type-classes-instances"},{"level":3,"text":"Type Class: Show","id":"type-class-show"},{"level":3,"text":"Type Class: Monoid & Num","id":"type-class-monoid-num"},{"level":3,"text":"Type Class: PrintAll","id":"type-class-printall"},{"level":3,"text":"Type Class: Type Equality!","id":"type-class-type-equality"},{"level":2,"text":"Goal: Higher-Order Type Classes","id":"goal-higher-order-type-classes"},{"level":2,"text":"Aside: What is a kind?","id":"aside-what-is-a-kind"},{"level":2,"text":"Aside: Higher-Kinded Types in Java","id":"aside-higher-kinded-types-in-java"},{"level":2,"text":"Subgoal: Extending ParsedType to support HKTs","id":"subgoal-extending-parsedtype-to-support-hkts"},{"level":2,"text":"Aside: Kind-checking Java-embedded HKTs","id":"aside-kind-checking-java-embedded-hkts"},{"level":2,"text":"Examples: Higher-Kinded Type Clases","id":"examples-higher-kinded-type-clases"},{"level":3,"text":"Type Class: Traversable","id":"type-class-traversable"},{"level":3,"text":"Type Class: Functor, Applicative, Monad","id":"type-class-functor-applicative-monad"},{"level":2,"text":"Recap","id":"recap-3"},{"level":2,"text":"Conclusion","id":"conclusion"},{"level":3,"text":"Future work","id":"future-work"},{"level":3,"text":"Related Work","id":"related-work"},{"level":2,"text":"Annex: Context Instances","id":"annex-context-instances"},{"level":2,"text":"Annex: Overlapping Instances","id":"annex-overlapping-instances"}]}}