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>

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

7 comments

Markdown is supported

exFalsocommented3 days ago

Nice! Although this isn't quite proper higher kinded types, it's not truly parametric in B. Good news is that people are working on it, if you look at the TODO list, it seems it's coming soon!

Completely unrelated sidenote: if you like this sort of hackery, I've always wanted to try something but never had the time: I'm conjecturing that with async Rust where async Futures are Clone, we could implement monadic do notation using the mother of all monads idea. Could be a fun project

HugoPeters1024commented3 days ago

@exFalso
Nice! Although this isn't quite proper higher kinded types, it's not truly parametric in B. Good news is that people are working on it, if you look at the TODO list, it seems it's coming soon!

Completely unrelated sidenote: if you like this sort of hackery, I've always wanted to try something but never had the time: I'm conjecturing that with async Rust where async Futures are Clone, we could implement monadic do notation using the mother of all monads idea. Could be a fun project

Thanks for you comment! What exactly do you mean with it being not truly parametric in B? Regarding the mother of all monads, that's a cool concept. Too bad that the IO-pandora box has already been opened for rust :)

pchampincommented2 days ago

Interesting read, thanks.
Small typo: the associated type in the declaration of Generic1 is named R, should be I.

HugoPeters1024commented2 days ago

@pchampin
Interesting read, thanks.
Small typo: the associated type in the declaration of Generic1 is named R, should be I.

Thanks for the kind words, typo is fixed :)

exFalsocommented2 days ago

@HugoPeters1024

@exFalso
Nice! Although this isn't quite proper higher kinded types, it's not truly parametric in B. Good news is that people are working on it, if you look at the TODO list, it seems it's coming soon!

Completely unrelated sidenote: if you like this sort of hackery, I've always wanted to try something but never had the time: I'm conjecturing that with async Rust where async Futures are Clone, we could implement monadic do notation using the mother of all monads idea. Could be a fun project

Thanks for you comment! What exactly do you mean with it being not truly parametric in B? Regarding the mother of all monads, that's a cool concept. Too bad that the IO-pandora box has already been opened for rust :)

Ah my bad, didn't see the Plug action, thought B is bound by a Functor associated type. Yeah this works, sweet!

Cypher1commentedabout 11 hours ago

Copied all the code into this playground for easy viewing and play.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=f12fcdd7b9962f2c2a1e443b6ff6ed01

Made two changes: 1) switch from println! to dbg! which I feel is cleaner, 2) use .to_string()

HugoPeters1024commentedabout 4 hours ago

@Cypher1
Copied all the code into this playground for easy viewing and play.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=f12fcdd7b9962f2c2a1e443b6ff6ed01

Made two changes: 1) switch from println! to dbg! which I feel is cleaner, 2) use .to_string()

Thanks for your suggestions! Especially the .to_string() method is something I will use from now on