Hugo's Blog

rust

Higher Kinded Types in Rust

Option wearing a crown

Introduction

Recently I have finally taken it upon myself to start learning rust. In the process of writing a vulkan raytracer in C++ I got so incredibly fed up with its tedious memory management, header/source duplication, and most of all bad IDE tooling, that I had to find something better. Rust had been the common subject of chatter around me and so I decided to see what all the fuss was about.

The first thing I noticed was that the tooling was incredibly effective and simple to set up. Never before had it taken me that little time to add a new language server to my Neovim setup. Moreover, the speed and helpfulness is amazing.

Hello world and printing some prime numbers came and went quickly. Time to mess around with some feature that caught my eye: associated types. Is rust the best of haskell and c++ together? Let's see if we can make our beloved Functor, Applicative, Monad hierarchy is this new world.

I have to mention first of all this post by Edmund Smith from whom I've stolen a few core traits needed to make this work. But I believe that in the end I ended up with a simpler, more elegant solution and therefore I think this post adds something to the discussion.

Higher kinded types

The first thing we need to realize is that a Functor is not defined over a traditional 'complete' type. Instead it is defined over a type with kind * -> *. An example would be Maybe, or as Rustians like to call it: Option. Take a look at the definition of Functor in haskell

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

We expect f to be type to which we can still apply another type. And there lies our first problem, we lack this ability in Rust. There are proposals to add this functionality and whilst certainly not trivial, there seems to be little reason to suspect that this feature will conflict with the core language principles.

However, for the time being we need to hack it in ourselves. Copying from Edmund, I've decided upon two traits that just implement the associated type magic needed for our purposes. You see, at no time do we actually need the unapplied, generic Option type, as long as we can convert an Option<A> to an Option<B>

For comparison, here is how we build our needed types in haskell:

type building haskell

And this is how we are going to do it in rust:

type building in rust

Administrative traits: Generic1 and Plug

To facilitate said type construction/destructing, we need two administrative traits with an associated type. Users need to implement these traits on their types before they can start making implementing any other traits that operate on higher kinded types.

The first of these is Generic1, which allows us to take the A out of Option<A>, or rather the type (I)nside:

trait Generic1 {
    type I;
}

impl<A> Generic1 for Option<A> {
    type I = A;
}

Secondly, we need a way to replace the inner type of Option. We do that using the trait Plug:

trait Plug<B> {
    type R;
}

impl<A, B> Plug<B> for Option<A> {
    type R = Option<B>;
}

// In other words
// <Option<A> as Plug<B>>::R == Option<B>

Note that we have to trust the user here to correctly implement these traits in order to actually get a correct implementation of the upcoming traits. But more tragically, the typechecker is now blissfully unaware that the resulting type is still an instance of Option, making it often impossible to derive the types of expressions.

Functor

With the type management traits in place, we can define and implement the Functor trait quite easily, albeit syntactically a bit of a mess.

trait Functor {
    fn fmap<B>(&self, f: &dyn Fn(&<Self as Generic1>::I) -> B) -> <Self as Plug<B>>::R
        where Self: Plug<B> + Generic1;
}

impl<A> Functor for Option<A> {
    fn fmap<B>(&self, f: &dyn Fn(&<Self as Generic1>::I) -> B) -> <Self as Plug<B>>::R {
        // Apply the function over the contained value, if there is one
        match self {
            None => None,
            Some(v) => Some(f(v)),
        }
    }
}

Applicative

This one is arguably the ugliest to look at. For clarity, let me also give you the much more sane haskellian type signature for the function ap:

(<*>) :: Applicative f => f (a -> b) -> f a -> f b

trait Applicative {
    fn ap<A, B, F: Fn(&A) -> B>(x: &<Self as Plug<F>>::R, arg: &<Self as Plug<A>>::R) -> <Self as Plug<B>>::R
        where Self: Plug<A> + Plug<B> + Plug<F>;

    fn pure(x: Self::I) -> Self
        where Self: Generic1;
}

impl<A> Applicative for Option<A> {
    fn pure(x: <Self as Generic1>::I) -> Self {
        Some(x)
    }

    fn ap<A2,B,F: Fn(&A2) -> B>(x: &<Self as Plug<F>>::R, arg: &<Self as Plug<A2>>::R) -> <Self as Plug<B>>::R {
        match (x, arg) {
            (None, _) => None,
            (_, None) => None,
            (Some(f), Some(v)) => Some(f(v))
        }
    }
}

Monad

And finally, Monad, in the case of Option this will be very similar to Functor. The only difference is the lack of necessity to wrap the result in a Some, since that is now the responsibility of the provided function.

trait Monad {
    fn bind<B>(&self, f: &dyn Fn(&Self::I) -> Self::R) -> Self::R 
        where Self: Plug<B> + Generic1;
}

impl<A> Monad for Option<A> {
    fn bind<B>(&self, f: &dyn Fn(&<Self as Generic1>::I) -> <Self as Plug<B>>::R) -> <Self as Plug<B>>::R { 
        match self {
            None => None,
            Some(v) => f(v),
        }
    }
}

Using it (warning: brain damage)

Let see if we can actually write some code using our new traits. Note that the following snippet has as little type signatures as possible whilst being a valid rust program.

fn main() {
    let x = Some(5);
    let y = x.fmap(&|i| i+1);
    let z = x.bind(&|_| Applicative::pure(String::from("bound!")));

    let x2 : Option<i32>= None;
    let y2 = x2.fmap(&|i| i+1);
    let z2 = x2.bind(&|_| Applicative::pure(String::from("bound!")));

    let g: Option<&dyn Fn(&i32) -> String> = Some(&|i| format!("{}={}", i, i));
    let g_eval = <Option<&dyn Fn(&i32) -> String> as Applicative>::ap(&g, &Some(69));

    println!("x: {:?}, x2: {:?}, y: {:?}, y2: {:?}, z: {:?}, z2: {:?}, geval: {:?}", x, x2, y, y2, z, z2, g_eval);
}

Which produces the following output:

x: Some(5), x2: None, y: Some(6), y2: None, z: Some("bound!"), z2: None, geval: Some("69=69")

So yes! You can use higher kinded types in rust. Whether you should I will leave up to you. But it certainly doesn't seem like a very attractive option for most projects considering the syntactic noise of the implementation, a typechecker that gets often confused and requires help, as well as error messages that don't make much sense. Especially the last is a shame since extremely helpful error messages is what rust is known for, and I wholeheartedly agree (under normal circumstances).

last modified: May 31, 2022 at 12:21