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 type-level defunctionalisation1 (comment link). /u/Krautoni also shared that Arrow-KT also uses defunctionalisation to implement HKT atop Kotlin’s type system and GHC uses defunctionalisation to lower redacted2 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>;
}

Zero-Sized Tokens

The first part is

// `Option` has the kind `Type -> Type`,
// we'll represent it with `OptionFamily`
struct OptionFamily;

Where we use a zero-sized 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 zero-sized 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 zero-sized 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 zero-sized 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 Haskell3 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 meta-programming in Rust (I bet you didn’t see that coming!4). Non-generic 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 type-level syntax is way more verbose. This makes anything but the simplest generic meta-programs almost inscrutable, so I don’t recommend using generic meta-programming unless you need to.

Earlier in this post I said:

and GHC uses defunctionalisation to lower redacted to 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 traits 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 type-level 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 kind Type -> 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

image tooltip here

Ok rustc… I’ll fix that error

// Note: in actual code you may want to use `fn() -> E`,
// to side-step 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 HKT-like 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 type-families, an experimental crate that implements the ideas outlined in this blog post.

You can discuss this on reddit here, on users.rust-lang.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 meta-programming. 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 proc-macro that compiles a sub-set of Rust to type-level code! This makes it really easy to write maintainable type-level code. (back)

4 Unless of course you are /u/Michael-F-Bryan! who mentioned how close this felt to template meta-programming in C++ (back)