This work is marked with CC0 1.0
This work is marked with CC0 1.0
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.
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.
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.
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 dont 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 garantee 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 kinds3, 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.
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
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!