Generalizing over Generics in Rust (Part 1.5): Mechanisms
Do you want to use Higher Kinded Types (HKT
) in Rust? Are you tired of waiting for GAT
? Well, this is the place to be.
This is part 1.5 in a series about emulating Higher Kinded Types in Rust, I’d encourage you to read Part 1 for background before reading this.
Before we begin, I’d like to give credit where credit is due. I first heard of the idea of type families from nikomatsakis’ blogs on type families and higher kinded types from back when GATs was called ATCs (Associated Type Constructors). The ideas from Part 1 where largely adapted from those posts to fit stable Rust.
Additional Readings: In the comments of Part 1, /u/LPTK shared some literature on this topic from OCaml: Lightweight Higher Kinded Polymorphism, what we are doing is called typelevel defunctionalisation^{1} (comment link). /u/Krautoni also shared that ArrowKT also uses defunctionalisation to implement HKT
atop Kotlin’s type system and GHC uses defunctionalisation to lower redacted^{2} to GHC core. All of these are very interesting, and are definitely worth reading.
In Part 1 I introduced the idea of type families, but without much explanation about why they worked, let’s dig in now!
// `Option` has the kind `Type > Type`,
// we'll represent it with `OptionFamily`
struct OptionFamily;
// This trait represents the `kind` `Type > Type`
pub trait OneTypeParam<A> {
// This represents the output of the function `Type > Type`
// for a specific argument `A`.
type This;
}
impl<A> OneTypeParam<A> for OptionFamily {
// `OptionFamily` represents `Type > Type`,
// so filling in the first argument means
// `Option<A>`
type This = Option<A>;
}
ZeroSized Tokens
The first part is
// `Option` has the kind `Type > Type`,
// we'll represent it with `OptionFamily`
struct OptionFamily;
Where we use a zerosized type as a token to represent some idea, in this case a kind Type > Type
. This is actually a common feature of Rust, this is how functions are implemented. For example:
fn foo() {}
foo
is a zerosized value that has a unique type (In errors foo
’s type shown as fn() {foo}
). Note this isn’t fn()
, a function pointer, but some anonymous zerosized type. Closures are implemented in a similar way. This allows Rust to minimize the size of objects, and more easily optimize away function and closures calls (For example, in iterator chains). We can also use this idea of zero sized tokens to represent some global resource, for example a Global
allocator. So overall zerosized tokens are a general concept that can be used in a variety of places.
Traits are Functions Declarations and Impls are Function Definitions
Here I think it’s interesting how similar Haskell^{3} is to Rust.
 Function declaration
one_param :: Family > Type > Type
 Function definition
one_param OptionFamily a = Option a
// function declaration
pub trait OneTypeParam<A> {
type This;
}
// function definition
impl<A> OneTypeParam<A> for OptionFamily {
type This = Option<A>;
}
O.o how similar! This is the core idea behind generic metaprogramming in Rust (I bet you didn’t see that coming!^{4}). Nongeneric traits represent a function with a single input, the type that they are implemented on. Each generic parameter increase the number of inputs to the function by one. Each associated type models an output. So each “function” can have any number of inputs and outputs.
So by having one generic parameter and one associated type, OneTypeParam
has two inputs and one output, just like one_param
in Haskell! Also like in Haskell, this definition is split from the declaration.
However there is one minor difference and one major difference. The minor difference: in Rust you can have multiple “return” types. Each return type also has a name. In Haskell, this can be modelled using records, so the difference isn’t significant, but it’s worth mentioning. The major difference: the Rust typelevel syntax is way more verbose. This makes anything but the simplest generic metaprograms almost inscrutable, so I don’t recommend using generic metaprogramming unless you need to.
Earlier in this post I said:
and GHC uses defunctionalisation to lower
redactedto GHC core
The actual comment is a spoiler for what’s upcoming in this post! I’ll fill in the blanks afterwards :).
Well, let’s fill in the blanks, spoiler’s over!
and GHC uses defunctionalisation to lower type classes to GHC core
Since trait
s are Rust’s version of type classes in Haskell, this makes sense. They are doing this same thing, so it makes sense that type classes are implemented like typelevel functions in Haskell.
Result: Type > Type > Type
Let’s tie this up in a bow with Result
. In Part 1 I said:
Result
has the kindType > Type > Type
So if we want to model Result
in it’s most general fashion, we need to model a function that takes two additional parameters:
struct ResultFamily;
trait TwoTypeParam<A, B> {
type This;
}
impl<T, E> TwoTypeParam<T, E> for ResultFamily {
type This = Result<T, E>;
}
What happens when we try to implement ResultFamily
for OneTypeParam
, just for shits and giggles?
impl<T, E> OneTypeParam<T> for ResultFamily {
type This = Result<T, E>;
}
error[E0207]: the type parameter `E` is not constrained by the impl trait, self type, or predicates
> src/lib.rs:7:9

7  impl<T, E> OneTypeParam<T> for ResultFamily {
 ^ unconstrained type parameter
error: aborting due to previous error
Ok rustc… I’ll fix that error
// Note: in actual code you may want to use `fn() > E`,
// to sidestep drop check, but that's not too important for us
struct ResultFamily<E>(PhantomData<E>);
impl<T, E> OneTypeParam<T> for ResultFamily<E> {
type This = Result<T, E>;
}
And that’s how we get the implementation shown in Part 1. But why does this work? Because, like traits, we can think of a generic struct
as a function. Each generic parameter is is an input, but struct
“functions” have only one output (the struct itself). So instead of ResultFamily: Type
it is now ResultFamily: Type > Type
. If we look a the broader picture, we see that we’ve transformed Result: Type > Type > Type
into ResultFamily: Type > Type
. This is currying in action! Just like doing the following in normal Rust.
fn curry_result(
result: impl FnOnce(Type, Type) > Type,
e: Type
) > impl FnOnce(Type) > Type {
let result_family = move t result(t, e);
result_family
}
Of course we could curry the other parameter instead, like so:
struct ResultFamily<T>(PhantomData<T>);
impl<T, E> OneTypeParam<E> for ResultFamily<T> {
type This = Result<T, E>;
}
And depending on which one we use, we would have different semantics.
Usage
I mentioned in the last post that using this method requires a lot of bounds. Let’s see what I meant by that.
Let’s write a function that composes two closures that return monads. Here we don’t really care about how this is implemented (although I will provide the implementation in the end), but more about the signature and everything required for that.
Let’s start with the skeleton with a HKTlike syntax, and we’ll reify it into our definition of Monad
from part 1.
fn compose_monad<M, F, G, A, B, C>(
monad: M,
f: F,
g: G
) > impl FnOnce(A) > M<C>
where
F: FnOnce(A) > M<B>,
G: FnOnce(B) > M<C>,
{
move a f(a).bind(g)
}
let plus_one_times_two = compose_monad(
OptionFamily,
x: u32 x.checked_add(1),
x: u32 x.checked_mul(2)
);
First: of course this doesn’t compile. It’s not even valid Rust syntax. But this is what HKT could look like in Rust. Second: Lots of type parameters! Let’s see what they all mean:
 M  What monad?
Option
,Result<_, E>
,Vec
, something else?  F  The first closure that will be applied
 G  The second closure that will be applied
 A  The parameter for the first closure
 B  The parameter for the second closure, and what’s contained in the monadic output of the first closure
 C  what’s contained in the monadic output of the second closure
Now how to we reify this? First we know that M
must be a monad, so let’s introduce that bound, and Monad
implies OneTypeParam
, so we can use the This
type alias to represent M<A>
, M<B>
, and M<C>
.
fn compose_monad<M, F, G, A, B, C>(
monad: M,
f: F,
g: G
) > impl FnOnce(A) > This<M, C>
where
M: Monad<A, B> + Monad<B, C>,
F: FnOnce(A) > This<M, B>,
G: FnOnce(B) > This<M, C>,
{
move a f(a).bind(monad, g)
}
let plus_one_times_two = compose_monad(
OptionFamily,
x: u32 x.checked_add(1),
x: u32 x.checked_mul(2)
);
Notice how we needed to declare Monad
twice, for each pair of applications we need. This doesn’t scale well as complexity increases. It also exposes implementation details of this function, which is also bad. Finally (and most importantly) we need the ugly This<T, U>
syntax instead of the nice T<U>
syntax.
Next Time
Next time in Part 2, we’ll properly introduce GATs and discover a way to reduce the number of required bounds when using HKT
in Rust.
If you can’t wait and must know more, check out typefamilies
, an experimental crate that implements the ideas outlined in this blog post.
You can discuss this on reddit here, on users.rustlang.org here, or twitter here
Footnotes
^{1} Eh, functions at the type level, what are these people on about. Rust doesn’t have functions at the type level /s. (We’ll explore this in this post) (back)
^{2} The actual comment is a spoiler for what’s upcoming in this post! I’ll fill in the blanks afterwards :). If you are fine with a minor spoiler, here’s the comment link. /u/Karutoni also provided a YouTube link to how Haskell does type inference, which goes into more details. (back)
^{3} Although I’m using Haskell here, I recommend you use Prolog to model out your generic metaprogramming. It’s far closer to how the trait solver actually works, so it will give better feedback on what’s possible and what isn’t. edit: /u/jswrenn showed off tyrade a procmacro that compiles a subset of Rust to typelevel code! This makes it really easy to write maintainable typelevel code. (back)
^{4} Unless of course you are /u/MichaelFBryan! who mentioned how close this felt to template metaprogramming in C++ (back)