jamie-blogs

alt. title: Forcefully Haskell-fying Rust, for Fun and Profit

If you're as much of a rust fanatic as I am you've probably realized that generics are really cool. In my opinion, rust's composition-based parametric polymorphism is one of the best things its inherited from its functional roots. Today I want to talk about what it left out, and hopefully expand how you think about type systems.

Proper Types

When we talk about types, we often mean something like this:

struct MyData {
	name: String,
	val: i32
}

This is a simple collection of data. The properties of this type are completely static— name will always be a String and val will always be an i32. We call these proper types. They are in a fixed and usable state; in other words, we know everything we can know about them.

Types.. kinda

Lets generalize this type to hold any value we could want:

struct MyData<T> {
	name: String,
	val: T
}

Now this type can composed of any other type, and the “type” T is actually just a placeholder for what we could later place inside this.

So.. this clearly doesn't fit the definition of a proper type that we previously defined, so what is it? Lets try analyzing what the compiler does with this type under the hood. Lets take the following code:

let data_a = MyData::new("asdf".into(), 12);
let data_b = MyData::new("asdf".into(), true);

And try searching for a MyData symbol:

nm target/debug/higher_orders_types | grep MyData

And we should see some output like this:

_ZN4core3ptr59drop_in_place$LT$higher_orders_types..MyData$LT$i32$GT$$GT$17h08f26c464aa8b7e0E
_ZN4core3ptr60drop_in_place$LT$higher_orders_types..MyData$LT$bool$GT$$GT$17hf107324ff7a39b31E

Bingo!

These lines say MyData$LT$i32 and MyData$LT$bool, so we can see that rust will actually generate concrete types for whatever gets used inside the generic! [^1]

Lets generalize this idea back into a type theory context: we can say that MyData is a special kind of type, that takes a proper type, and returns a proper type.

Improper Types

Just with higher-order-functions, we can see that this type is a level above concrete types. These are called kinds. A kind is a type constructor that takes a type, and produces a new type.

So now that we have a new concept to play with, what can we do with it? Well, lets see what Haskell does with it:

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

If you don't know any haskell, this likely looks very arcane to you. Lets write it in the style of rust:

trait Functor {
	fn fmap<A, B>(
		f: impl Fn(A) -> B, 
		Self<A>
	) -> Self<B>;
}

So fmap takes a function of A -> B and a Self<A>, maps said function on the inner value, and returns a Self<B>. If you try to compile this, you'll get an error akin to “Self takes 0 parameters.” Rust doesn't have a notion of kinds, only parametric polymorphism, so we cant refer to a kind as something on its own. So making this trait will be a little messier, but we can still do it:

trait Functor<A, B>: Sized {
    //type Ma; will be Self
    type Mb;
    
    fn fmap(f: impl Fn(A) -> B, rhs: Self) -> Self::Mb;
}

We can't guarantee that Mb will be Self<B>[^2], but we can at least now use this trait on Option.

impl<A, B> Functor<A, B> for Option<A> {
    type Mb = Option<B>;

    fn fmap(f: impl Fn(A) -> B, rhs: Self) -> Self::Mb {
        match rhs {
            Some(v) => Some(f(v)),
            None => None,
        }
    }
}

Actually, while we're rusti-fying this, lets turn it into a method.

fn fmap(self, f: impl Fn(A) -> B) -> Self::Mb {
    match self {
        Some(v) => Some(f(v)),
        None => None,
    }
}

You've most definitely realized at this point that this is identical to a method that already exists, map. If you squint a little, you'll even notice that lots of rust methods come from haskell typeclasses!

Since haskell supports kinds[^3], its able to soundly model these sorts of actions. Its so capable that haskell actually uses a monad to introduce side effects into a purely functional language! Its monads all the way down.

Footnotes

1. in this case you can see that rust is actually generating the drop_in_place function, so that it can call any destructors when these variables go out of scope
2. there are actually a lot of ways you could go about solving this, decided to go with a relatively naive/straightforward path
3. its probably more correct to say “haskell supports curried type constructors”
4. i lightly refered to a type theory page (mostly just to make sure i was using the right words) on wikipedia when i was writing this, check that out for more fp mumbo-jumbo!

maybe sometime ill write more about monads for real, but thats a whole thing that i didnt want to get into. the point of this article was to bridge the gap and expose some of rusts fp roots, and why i think its so cool. thnx for reading! <3