Higher Kinded Types in Rust

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:

And this is how we are going to do it 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>

Functor

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

(<*>) :: 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

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)

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).