Rust Type System Catches Data Races in Parallel Redux Reducers

The Problem: Parallel Reducers with Shared State

Data races in concurrent systems are notoriously hard to debug. They only appear under load, vanish when you attach a debugger, and take teams days to track down. Rust's borrow checker handles most value-level races, but what about higher-level patterns like parallel Redux reducers?

Redux is a state management pattern where a single store holds all state, and state transitions happen through pure reducer functions (state, event) -> new state. These reducers must be deterministic and side-effect-free. In a typical Redux setup, multiple reducers each handle a distinct slice of the state (e.g., solar, battery, meter). Since reducers are independent, they can run in parallel to reduce latency.

But parallel + shared state = data races. If one reducer accidentally writes to another's slice, you get non-deterministic outputs. Most languages rely on developer discipline or runtime checks. Rust's type system can encode the property directly: the compiler refuses to build code that would race.

The Failed Attempt: AllDistinct

Corgié's first idea was a trait AllDistinct that asserts no two reducer types target the same slice type. The approach: recursively walk a tuple of reducer types and check that each head's slice is different from every slice in the tail. In pseudo-Rust:

trait AllDistinct {}
impl AllDistinct for () {}
impl AllDistinct for (H, Tail)
where
    Tail: AllDistinct,
    H: NotIn,
{}

The problem: NotIn requires type inequality H != T for each element in the tail. Rust's trait system has no syntax for that. The unstable feature negative_impls exists but remains behind coherence concerns. The trait system is monotonic: adding new impls can only enable more code, never disable existing code. Negative reasoning would break that property.

The Pivot: Bijection Instead of Negation

Instead of proving "no duplicates" (a negative), Corgié reformulated the problem as "each state slice has exactly one matching reducer" (a positive bijection). This is logically equivalent: if every slice maps to exactly one reducer, then no two reducers share a slice.

To implement this, he needed a list structure the compiler can walk recursively. Tuples don't work (each arity is a distinct type). Enter HLists (heterogeneous lists), a known pattern from the frunk crate. An HList is a linked list where each cell holds a different type:

struct HCons { head: H, tail: T }
struct HNil;

A three-element HList looks like:

HCons>>

The compiler can recursively traverse HLists via trait impls: one base case for HNil, one recursive step for HCons.

The Implementation: Lookup and Trait Coherence

Corgié's approach: walk the state's slice list (declared as an HList of slice types), and for each slice type, find the reducer in the reducer tuple whose associated Slice type matches. The lookup uses a trait FindReducer that returns a witness (a zero-sized type) proving the reducer exists.

trait FindReducer {
    type Reducer;
    fn find_reducer(&self) -> Self::Reducer;
}

The trait is implemented for HNil (no match → compile error) and HCons (if H::Slice == S, use it; else recurse). If two reducers match the same slice, Rust's trait coherence rules produce an ambiguous impl error at compile time. If zero match, the trait bound is unsatisfied. No runtime checks needed.

The Result: Compile-Time Guarantees

With this design, the parallel root reducer is built from a list of slice reducers and a list of slices. The compiler checks the bijection at compile time. If the check passes, parallel execution is sound. If it fails, the program doesn't compile.

Corgié's ruxe library demonstrates this with a concrete example: a CombineReducers struct that takes a tuple of reducers and a slice list, and implements Dispatch for it. The dispatch function iterates over the slice list, looks up each reducer, and runs the reducer on the corresponding slice in parallel.

The key insight: Rust's trait system can express complex invariants about type-level relationships, even without negative reasoning, by reframing the problem as a positive bijection. This pattern is generalizable to other domains where you need to enforce disjointness or uniqueness at compile time.

Why It Matters

For developers building concurrent systems in Rust, this approach offers a way to encode safety invariants directly in the type system, eliminating entire classes of bugs at compile time. It's a concrete example of how Rust's trait system can go beyond simple bounds to enforce domain-specific correctness properties.

The technique is not limited to Redux. Any system with parallel access to partitioned state (e.g., sharded databases, parallel data processing pipelines) could benefit from similar compile-time disjointness checks. The HList pattern and trait-based lookup provide a reusable foundation.

What's Next

Corgié's ruxe library is a learning project, but the pattern is production-ready for anyone willing to adopt HLists and trait-based type-level programming. The full source code and blog post are available at the link below. For developers interested in type-level shenanigans, this is a must-read.