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

*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!