Overview
The DeepCausality project is proud to announce deep_causality_haft (Higher-Order Abstract Functional Traits), a standalone crate that brings rigorous functional programming abstractions to Rust. HAFT serves as the mathematical engine room for DeepCausality, enabling the complex, context-aware reasoning capabilities of the core library.
While Rust’s type system is incredibly powerful, it famously lacks native support for Higher-Kinded Types (HKTs). This post explores why the DeepCausality needed them, how we emulated them using the Witness Pattern, and how this enables Type-Encoded Effect Systems.
1. The Fundamental Problem: Abstraction over Containers
In Rust, you can easily write a function generic over a type T. But you cannot easily write a function generic over a container of T.
Suppose you want to write a function double_inner that takes a container of integers and doubles them. You want it to work for Option<i32>, Vec<i32>, Box<i32>, and Result<i32, E>.
Standard Rust requires you to implement this for each type or define a custom trait for every specific behavior. You cannot express “Any type constructor F<_> that has a map function”.
// Ideal (but impossible in standard Rust syntax):
fn double_inner<F>(container: F<i32>) -> F<i32>
where F: Functor
{
container.map(|x| x * 2)
}
This limitation becomes critical when building a causal reasoning engine. We need algorithms that can operate uniformly whether they are processing a simple value, a fallible computation, a physics process matrix, a quantum state, or a complex causal process with history.
2. The Solution: The Witness Pattern
To solve this, HAFT leverages the Witness Pattern (also known as the “Family” pattern) combined with Generic Associated Types (GATs).
Instead of passing the type constructor Option directly, we pass a zero-sized struct OptionWitness that represents it.
The Mechanism
First, we define the HKT trait, which maps a witness to its underlying type constructor:
pub trait HKT {
type Type<T>;
}
Then, we implement this for our witness structs:
pub struct OptionWitness;
impl HKT for OptionWitness {
type Type<T> = Option<T>;
}
pub struct VecWitness;
impl HKT for VecWitness {
type Type<T> = Vec<T>;
}
Now OptionWitness is a concrete type that acts as a proxy for the concept of “Option-ness”.
3. Algebraic Traits: Functor and Monad
With the HKT machinery in place, we can define standard functional traits.
Functor
A Functor is anything that can be mapped over. Notice how the trait is generic over the Witness F:
pub trait Functor<F: HKT> {
fn fmap<A, B, Func>(m_a: F::Type<A>, f: Func) -> F::Type<B>
where
Func: FnMut(A) -> B;
}
Now we can write our generic function from before:
use deep_causality_haft::{Functor, HKT, OptionWitness, VecWitness};
fn double_inner<F>(container: F::Type<i32>) -> F::Type<i32>
where
F: Functor<F> + HKT
{
F::fmap(container, |x| x * 2)
}
fn main() {
let opt = Some(10);
let vec = vec![10, 20];
// Same function logic, different containers!
let opt_res = double_inner::<OptionWitness>(opt);
let vec_res = double_inner::<VecWitness>(vec);
}
Monad
The Monad trait adds the ability to chain operations that return new contexts (bind or flat_map). This is the foundation of the DeepCausality inference engine, allowing us to chain causal steps where any step might fail, log data, or access state.
4. Solving Dimensionality: The Arity Problem
Real-world types are rarely as simple as Option<T>. They often have multiple generic parameters.
Consider Result<T, E>. It has Arity 2.
To make Result behave like a Monad (which expects Arity 1: M<T>), we must “fix” the error type E. HAFT introduces Arity Traits (HKT2, HKT3, etc.) to handle this via partial application at the type level.
// HKT2 fixes one parameter (F) and leaves one open (T)
pub trait HKT2<F> {
type Type<T>;
}
pub struct ResultWitness<E>(PhantomData<E>);
impl<E> HKT2<E> for ResultWitness<E> {
type Type<T> = Result<T, E>;
}
This allows us to treat Result<T, String> as a Monad just like Option<T>, simply by using ResultWitness<String>.
5. Type-Encoded Effect Systems
The ultimate goal of HAFT is to power Type-Encoded Effect Systems.
In complex systems, a computation isn’t just Input -> Output. It involves:
- Value: The result.
- Error: Failure modes.
- Logs: Audit trails.
- State: Markovian history.
- Context: Global configuration.
HAFT defines the Effect5 trait, which maps these requirements to an HKT5 witness.
pub trait Effect5 {
type Fixed1; // Error
type Fixed2; // Log
type Fixed3; // State
type Fixed4; // Context
// The Witness that combines these 4 fixed types with a 5th open 'Value' type
type HktWitness: HKT5<Self::Fixed1, Self::Fixed2, Self::Fixed3, Self::Fixed4>;
}
This abstraction allows deep_causality_core to implement a Causal Monad that is completely agnostic to the underlying storage details. Whether you are using a simple debug logger or a complex telemetry system, the causal logic remains pure, testable, and mathematically sound.
Conclusion
deep_causality_haft brings the rigor of Category Theory to Rust’s pragmatic type system. By solving the HKT problem and handling multi-parameter complexity, it allows engineers to build systems that are flexible, reusable, and provably correct.
Get Started with HAFT today!
- Explore the API Documentation.
- Review the examples.
- Join the community.
About
DeepCausality is a hyper-geometric computational causality library that enables fast and deterministic context-aware causal reasoning in Rust. Please give us a star on GitHub.
The LF AI & Data Foundation supports an open artificial intelligence (AI) and data community and drives open source innovation in the AI and data domains by enabling collaboration and the creation of new opportunities for all members of the community. For more information, please visit lfaidata.foundation.