· 6 min read ·

When Rust's Trait Solver Meets Higher-Kinded Types: A Story About Inductive Cycles and Compiler Grief

Source: lobsters

Rust’s type system is famously expressive, but it has a well-known gap: no native support for higher-kinded types. In most Rust circles this is a minor inconvenience, worked around with dyn Trait or just avoided entirely. But for people who want to encode Haskell-style abstractions, like Functor, Monad, or Traversable, the absence of HKTs is a wall they keep running into.

A recent post by harudagondi, Torturing rustc by Emulating HKTs, Causing an Inductive Cycle and Borking the Compiler, documents what happens when you push this emulation far enough: the compiler breaks. Not “gives you a cryptic error” breaks. Breaks as in hangs, panics, or produces wrong answers. That outcome deserves more unpacking than the original post’s comments section provides.

What Higher-Kinded Types Actually Mean

In Haskell, the Functor class is defined roughly as:

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

The f here is not a concrete type like Int or String. It is a type constructor, something of kind * -> *. Maybe qualifies. Vec qualifies (as []). Int does not. This distinction, called kindedness, is what allows Haskell to abstract over container shapes independently of what they contain.

Rust’s type system operates almost entirely at kind *. Every generic parameter T in a Rust function or struct is expected to be a fully concrete type. You cannot write:

trait Functor<F<_>> { ... } // not valid Rust

because F<_> is a type constructor, and Rust’s generics do not accept those as parameters. RFC 324 touched some related corners of the type system, and there were pre-RFC discussions about HKTs going back to 2014, but the feature has never been formally proposed in a complete form. The closest the language got was RFC 1598, which introduced Generic Associated Types (GATs), stabilized in Rust 1.65.0 in November 2022.

The GAT Emulation Pattern

GATs let you write associated types that are themselves generic, which opens the door to encoding type constructors as traits:

trait TypeConstructor {
    type Applied<T>;
}

struct VecConstructor;

impl TypeConstructor for VecConstructor {
    type Applied<T> = Vec<T>;
}

trait Functor {
    type Of<A>;
    fn fmap<A, B>(fa: Self::Of<A>, f: impl Fn(A) -> B) -> Self::Of<B>;
}

This is the approach taken by crates like higher and various blog post experiments. The Of<A> associated type acts as a stand-in for the applied type constructor. Vec<T>, Option<T>, Result<T, E> can all be given Functor implementations by defining Of<A> appropriately.

At first glance this works. The problem appears when you try to compose these abstractions, particularly when you want to state that one type constructor can be “applied inside” another, or when you need trait bounds that describe relationships between multiple constructors simultaneously.

Inductive Cycles in Trait Resolution

Rustc’s trait solver works by recursively decomposing obligations. To prove T: SomeTrait, it looks for an impl block, then tries to prove all the where clauses on that impl, then their requirements, and so on. This is a depth-first search.

The solver distinguishes between two kinds of cycles:

Coinductive cycles are cycles where the solver can assume the goal is true while proving it, which is valid for structural properties like Send and Sync auto traits on recursive data structures. A struct Node { next: Option<Box<Node>> } can be Send because the cycle is well-founded.

Inductive cycles are cycles in regular trait solving where the solver is trying to prove A: Trait and discovers that proving A: Trait requires proving A: Trait. The old solver (which uses a depth-limit and memoization) will either overflow its recursion counter and emit error[E0275]: overflow evaluating the requirement, or in pathological configurations, loop until it exhausts resources.

HKT emulation creates these cycles almost naturally. Consider adding a bound that says “the mapped type must also be a valid functor”:

trait Functor {
    type Of<A>;
    fn fmap<A, B>(fa: Self::Of<A>, f: impl Fn(A) -> B) -> Self::Of<B>
    where
        Self::Of<B>: Functor; // here's the trouble
}

Now proving Vec<i32>: Functor requires proving that Vec<B>: Functor for any B, which requires proving Vec<C>: Functor for any C, which recurses indefinitely. The bound is trying to express something reasonable (that fmap produces another fmappable thing) but the trait solver cannot see the well-founded structure here because the recursion is through a generic type parameter, not a concrete structural step.

What “Borking” the Compiler Looks Like

The failure modes vary depending on what exactly the code triggers:

  • Overflow error: The benign case. You get E0275 and rustc tells you to raise #![recursion_limit = "256"]. Raising the limit just delays the inevitable.
  • Internal Compiler Error (ICE): The solver reaches a state it did not anticipate and panics with thread 'rustc' panicked at 'assertion failed' or similar. These are bugs by definition; the compiler should always produce an error message, not crash.
  • Hang: The solver enters a loop that the recursion limit does not catch. This happens when the cycle detection itself is broken by the structure of the type-level program. The compiler simply stops making progress.
  • Unsound acceptance: Rarest and most dangerous. The solver incorrectly concludes that a trait is implemented when it is not, allowing code to compile that violates type safety invariants.

The last two are the genuinely concerning outcomes. A hang is user-hostile but recoverable. Unsoundness is a correctness bug in the compiler.

The New Trait Solver

The Rust compiler team has been working on a replacement trait solver since around 2022, tracked under the next-solver umbrella and the Chalk project. The new solver uses a different algorithm based on tabling (also called SLG resolution), which handles cycles more systematically by representing them as sets of constraints rather than recursion with memoization.

A key design change: the new solver treats more goals coinductively by default, which sidesteps many of the pathological cycle cases that plague the old solver. The tradeoff is that some programs that were previously rejected might now be accepted, and the semantics need careful validation.

As of early 2026, the new solver is available under the #![feature(next_solver)] nightly flag but is not yet stable. The Rust team’s formal model work is running in parallel, attempting to give the type system a rigorous specification so that solver behavior can be proven correct rather than just tested.

Why This Matters Beyond Curiosity

Experimenting with type system limits serves a real purpose. Every time someone discovers that a particular encoding breaks rustc in a novel way, that is a bug report in disguise. The cycle detection logic in the old solver has known gaps, and documenting new ways to expose them gives the compiler team concrete test cases.

Beyond bug reporting, the HKT problem in Rust keeps coming up because the abstractions people want to express are genuinely useful. Async Rust, in particular, would benefit from better type constructor abstraction. The inability to write a generic Monad bound over both Future and Option forces a lot of code duplication and limits how far libraries can abstract without resorting to macros.

Niko Matsakis wrote extensively about the design space around GATs and their limitations during the RFC process, and many of those concerns map directly onto the kinds of cycles that HKT emulation triggers. The gap between “GATs can express many things” and “GATs can express HKTs safely” is precisely the gap that breaks the solver.

The harudagondi post is a good concrete example of this gap, and it joins a long line of Rust type system archaeology posts that probe the edges of what the compiler can reason about. Whether you are interested in Rust’s theoretical underpinnings, the practical limits of GAT-based abstraction, or just curious about how a production compiler can be made to hang by carefully crafted trait bounds, the experiment is worth studying. The next-solver work is the most promising path toward a compiler that handles these cases gracefully, and its progress over the next year or two will determine how far generic Rust programming can actually go.

Was this interesting?