Generalizing over Generics in Rust (Part 1) - AKA Higher Kinded Types in Rust
rustyyato.github.io/type/system,type/families...Posted Feb 16, 2021, 6:13 PM UTC
Posted Feb 16, 2021, 6:13 PM UTC
This is unironically my idea of fun reading.
This is unironically my idea of fun writing. :)
This is a remarkable piece of insight. I love seeing creative solutions to hard problems, especially when you can look back and see that the solution was only natural. Kinds are "things" which map types to types and traits can have types as inputs (generic parameters) and types as outputs (associated types), so it makes sense that you can find a way to represent kinds with them.
I agree that you lose points on ergonomics, these things will probably be a massive pain to use in practice. You'd need some sort of language support or way to seamlessly integrate it with the rest of the language.
It's kinda like template metaprogramming in C++... What they are really looking for is traits and where clauses, but people were able to bodge around it using existing language features (templates, inheritance, specialisation, and sfinae). Template metaprogramming is also unergonomic and verbose, so they have that in common too.
I know some words in this article 🎉
well written and beautifully simple analogy. I didn't (and guess i still don't) know about HKTs.
I am working on a library that works with a trait P that is implemented by a struct generic over F (struct C<F> impls P). This causes my libraries structs' methods to be littered with additional generic parameters F (e.g. for an interpolation parameter between two C's).
If i read your post correctly, HKTs would apply to this pattern, yes?
Yes, I believe HKT would apply in this case. Would you mind sharing?
gladly! here is a recent post i made about it, looking for criticism. It links to the repo (not published on crates.io yet).
if you look at any of the Bezier types, you will see the trait bounds repeated everywhere
This doesn't look like something related to HKT. HKT is more useful for things like generalizing over containers, not eliding bounds. I don't know of a nice way to group together these sorts of bounds. Maybe with trait aliases?
thanks for having a look! i thought maybe there was a way since point types are basically just containers of generic coordinates. will take a look at trait aliases because the current solution just doesnt feel DRY
I feel like I can't really grasp what this is without some examples, can anyone name some things that would be possible with HKTs?
One usecase for HKT in Rust is a trait called Traverse. Before I explain Traverse, let's look at Iterator. With Iterator you can iter.collect::<Option<Something>>(), and this works for any Iterator<Item = Option<_>>, but what if you could do this, not just for Option, but for any type that implements a trait?
Without HKT, there isn't a good way to express this sort of relationship. With HKT, you can "collect" anything Traverse over a wrapper that implements Applicative. For example, Vec implements Traverse and Option implements Applicative. This means you could convert a Vec<Option<T>> to a Option<Vec<T>> where it is None if any of the inner Options are None.
This requires HKT to work nicely, but we can hack around it in Rust :). An example that doesn't really apply to Rust is: do notation in Haskell. do notation allows you to almost write in an imperative style in Haskell.
In the article I assume the motivation for HKT, because there are lots of nice resources online for the motivation, explanations of how HKT abstractions work, and how to think about these abstractions.
I wonder if you could bring it down another level for us mere humans and provide a simple playground example of this?
It's an idea that's a lot more commonplace in Haskell-land. Traverse can be understood in a multitude of ways. I'll give you one interpretation.
If you have:
T_input to Something<T_output>T_inputs ("Container<T_input>")Container has an impl for Traverse (which would have a method called traverse)With the above, you can get back a Something<Container<T_output>>.
Concrete example: I have a fn(u8) -> Option<char> and a Vec<u8>, I can call the traverse operation to get back a Option<Vec<char>>. Meaning, I take the function, apply it to every u8 in my Vec<u8>. If I ever get back None, my end result will be None, otherwise I'll get back Some([... a bunch of chars ...]).
More commonly would be mapping over a Vec, applying an operation that can fail (returns Result<T,E>) over all its elements, and if the operation fails, I get back Err(E). Traverse is one abstraction around this.
I'm probably completely wrong, but I think I remember seeing that flatten on Result and Option works similar to your example. Eg. <Vec<Result<u8>>.flatten() becomes Result<Vec<u8>>.
If yes, I assume thats just a special case that was implemented that way, but a generally useful one, nonetheless.
Thanks, I get it now
You can write code that's generic over Rc or Arc.
Can't you already do that by implementing a trait for both of them?
This won't work if the trait is not defined in the same crate because of the orphan rule.
But there is nothing stopping you from defining a RcFamily trait yourself and implementing this on them.
huh I was under the impression this wasn't possible, per https://www.fpcomplete.com/blog/monads-gats-nightly-rust/. I wonder what u/snoyberg would think about this post
u/YatoRust pointed out this approach to me in the previous Reddit thread. And now I notice that he's the OP on this article.
My overall thoughts on all of this are:
I still wouldn't use this in my Rust code today
I remember the days of emulating variadics in C++03; it was possible, but nobody wanted to touch that stuff.
Saving for when I have more functional programming background and can get this haha
Good article! I found myself banging my head trying to accomplish something like this not long ago and stumbled across the GAT stuff. Very cool to see that what I was trying to accomplish can be done in stable this way.
Having recently read rfc 1598, I did find the syntax in explaining kinds a bit confusing:
Result is Type -> Type -> Type
where the language in the rfc would say:
Result is Type, Type -> Type
which seems a bit less ambiguous to follow.
Looking forward to reading the next part and hoping this works well with lifetimes too :)
Heh, I'm just trying to follow the literature as close as reasonably possible for Rust, which leads to Type -> Type -> Type, I'll add a note about that.
Probably because Rust doesn't have native currying the second one feels "less ambiguous". It feels pretty natural in something like OCaml or Haskell, when you realize that
foo :: a -> b -> c
can be thought both as a function taking two arguments of some types a and b an returning something of type c and as a function that takes something of type a and return a function that takes something of type b and returns ... c.
like
foo x y == (foo x) y
(foo x) :: b -> c
I see that, but does the expression really apply to Result?
Thinking about this a bit more, I can see that `Result` can become some intermediate type constructor with only one parameter bound, and that in turn can become a type. Because it has two type args, it could even be visualized as a diamond with two different intermediate type constructors, that each do different things (the first intermediate specializing on T, the second specializing on E).
Yup. If you think about Result<T, E> as a function on types that takes two type arguments and returns concrete type ResultTE, then the same principle applies. With the similar partial application/currying (that is basically a specialization on one type parameter) Result<T, E> Int == ResultInt<E>.
You have a typo in the last paragraph of the first section:
Just one cinch, we Rust doesn’t know about kinds!
I don't think the "we" after the comma belongs there.
Ahhhhhhh
Fixed
Also, trait<A, B> Functor<A, B> for OptionFamily should be impl<A, B> Functor<A, B> for OptionFamily
Fixed
Also somewhere there is a "try it our yourself".
How did I miss soo many typos, I checked this over like 5 times for typos!
Edit: Fixed
fn map<F>(self, this: This<Self, A>, f: F) -> This<Self, B>
where
F: Fn(A) -> B + Copy;
Why is there a this parameter and a self parameter? How is this intended to be invoked?
The This "parameter" is actually a type alias for the associated type in Family. I defined it right after I defined Family. For example if Self is OptionFamily then This<Self, A> is Option<A>.
I've been borrowing your design but applying it to a continuation monad. I didn't bother with the self parameter at all. Is there any technical reason to want it?
However, I need extra bounds on things that you don't need in your category theory hierarchy. I have to wonder if I'm doing something wrong. For example, I opted not to put a Copy constraint on F, but instead I gave it a Clone constraint:
pub trait Functor<'a, A, B>: Family<A> + Family<B> {
fn map<F>(f: F, this: This<Self, A>) -> This<Self, B>
where
F: Fn(A) -> B + 'a + Clone,
A: 'a,
B: 'a;
That lifetime 'a is only there because the Cont type has a lifetime and didn't see any obvious way to make the impls work unless I had the lifetime in the trait. For instance, if I remove all the lifetimes from the traits and only introduce them at the impl, then I'll get an impl like this:
impl<'a, R: 'a, A: 'a, B: 'a> Functor<A, B> for ContFamily<'a, R> {
fn map<F>(f: F, this: This<Self, A>) -> This<Self, B>
where
F: Fn(A) -> B + 'a + Clone,
{
this.fmap(f)
}
}
But then the compiler says:
impl has extra requirement `F: 'a`
The only thing I can think to do, which I haven't fully explored yet, is moving F from the method to the trait itself. It seems to kind of work but with the caveat that each such F from the trait methods likely needs to be a distinct parameter and the constraints on it need to be in the outermost where clause of the trait.
So then by the time you get to Monad you have so many generic parameters because of plumbing all the parameters through the super traits. I stopped before I got Monad working but I think it had like 7 or 8 parameters.
To give you an example of where I stopped with this encoding here is Applicative with ?? where I stopped:
pub trait Applicative<A, B, F, G, C>: Functor<A, B, F> + Pure<A> + Pure<B>
where F: Fn(A) -> B + Clone,
G: Fn(A,B) -> C + Clone,
{
fn apply(a: This<Self, F>, b: This<Self, A>) -> This<Self, B>
where
Self: Applicative<F, A, ??, ??, C>,
A: Clone,
B: Clone,
{
Self::lift_a2(move |q: F, r| q(r), a, b)
}
fn lift_a2(f: F, a: This<Self, A>, b: This<Self, B>) -> This<Self, C>
where
Self: Pure<C>,
Self: Family<C>,
A: Clone,
B: Clone,
C: Clone;
}
It really feels like I'm missing a simple solution here.
You're welcome to take a look at my code here: https://github.com/dagit/rust-monads/blob/master/src/main.rs
Not This, this. map is usually a two-parameter function, right? opt.map(f). But this map has three parameters, named self, this, and f.
Oh, same thing. self is the family (OptionFamily), this is the actual value (Option<T>), and f is the function.
Is this the equivalent of C++'s template template syntax?
Pretty much, yes.
Oh, so this is type-level defunctionalisation! Nice, I didn't think about applying it to Rust, but it makes total sense!
It's similar to how Arrow-KT implemented HKTs on top of Kotlin's type system. You have to pass concrete witnesses around there, though, which you don't have to in Rust. Rust's compiler can use traits to figure out which function to call (Kotlin lacked traits, but they're implementing generic interfaces now, something that might end up being quite similar) so you can forgo witnesses.
It's interesting to note that GHC does exactly that when translating type classes to Haskell Core: they're defunctionalised. I think there was a great SPJ talk on that, but I can't find it…
That's facinating! Thanks for sharing, and also for sniping my next post with that note on type classes! They are very similar to traits, so it doesn't surprise me that they are lowered with defunctionalisation. If you do find a link, I'll be happy to include it in my next post.
I think this was the talk or near enough to it anyway. He basically explains how Core does use witnesses and passes them around by generating all kinds of additional bindings for every function that has a typeclass-constrained type variable.
In Kotlin you need to do that by hand all the way. In Rust, you need to do it half the way, by using traits.
Edit: oh, he also explains how Core is no more? I guess I'm getting old, and my Haskell days have long since passed :D
Thanks! I'll include it anyways, it looks interesting
I'm new to rust but shouldn't
trait<A, B> Functor<A, B> for OptionFamily {
be
impl<A, B> Functor<A, B> for OptionFamily {?
(same for trait<A, B> Monad<A, B> for OptionFamily { )
Ahhhhhh, thanks for catching this typo. Edit: Fixed
One is glad to be of service.
I'm looking forward to more articles.
I tried to learn rust by trying to port some Elm code and I failed miserably. I simply could not figure out how to implement a pipeline where one starts with a multiargument function and then constructs the result by applying the arguments.
In other words, given the equivalent Elm code: apply 1 (apply "foo" (\str int -> str ++ String.fromInt int))), how would one implement apply in rust?
That's difficult, and likely won't be possible for functions in general until we get varadic generics. This is will allow us to abstract over all function arguments (with the Fn* traits) and allow you to create an apply combinator.
:(
I was thinking of porting elm/parser to rust and I needed something like apply in order to implement the mechanism needed for the pipeline.
it's way too 3am for me to read this...
​
I'll come back to it tmr
[deleted]
I am not sure the problem is with HKT; I would think the problem is the variadic number of arguments.
This is the clearest I've ever seen HKTs explained.
Even though I don't think this is written very clearly it's still the best explanation of HKTs I've seen.
Do you have any suggestions for improvements? I'm just starting to blog so this is new to me.
Sure!
Values like
0,true, andxinx: boolare called terms
That bit's confusing. There's no 0 in x: bool as far as I can tell? And you're mixing up variable names and values or something?
I think you're just saying that values are terms. Is x really a term? Maybe this would be clearer (if correct).
In computer science lingo values like
0,true, and"hello"are called terms. To write code that works for all terms that are "the same" in some way we can use types. For example to write a function that works for all values that are signed 32-bit integers we use a variable parameter with typei32.fn works_with_all_signed_32bit_integer_values(x: i32) {}When we do that we can say that we have "generalised over terms". We've written code that works with all terms of a certain generic type.
We can go up a level. What if we want to write a function that works for all types that are "the same" in some way. In that case we can use generics and traits. For example to write code that works for all types that can be printed we add a generic type parameter and use the
Displaytrait.fn works_with_all_displayable_types<T: Display>(x: T) {}But what if we go up one level more! What if we want to write code that works for all type parameters that are "the same" in some way. What if we want the code to work for all
Tthat are of the formX<Y>, but we don't care whatXorYare? That's where HKTs come in.For example
Option<T>andanyhow::Result<T>both fit that pattern. Is there any way we can write code that works for both of them?But what exactly is the pattern
X<Y>? We can think about generic types as functions on types. For exampleOption<T>is a type function that takes the typeTand converts it into another type (Option<T>). It has the signatureType -> Type.Another example:
HashMap<K, V>takes two types and makes another one. Its signature is(Type, Type) -> Type.HKTs allow us to write code that is generic with respect to all types that have the same signature.
I don't fully understand them still so that may not be a great explanation.
Result is Type -> Type -> Type
I always hated this unnecessarily confusing Haskell syntax. Sure it's neat and elegant I guess. But people don't think about functions as a function of a function of a function or whatever. You do mention that it's the same as (Type, Type) -> Type later, but honestly I would just use that notation throughout and ditch Type -> Type -> Type. It's much easier to understand.
pub trait Family<A> {
As I understand it, Family is just for one specific family of types? If so it would be clearer if it were called something like MappableTypes or OptionLikeTypeFamily or SingleParamTypes or whatever. Unless "family" is some standard nomenclature in which case just explain:
"Family" is the standard word for a type that takes one type and converts it to another type, i.e. everything with a single type parameter
X<Y>.
I'll be honest, I didn't actually understand your post until I wrote all this, but I finally understand what a functor and monad is (and how absolutely terrible all explanations of functor and monads are) so thank you!
The whole introduction is soo nice, the update is heavily inspired by your work here
I always hated this unnecessarily confusing Haskell syntax. Sure it's neat and elegant I guess. But people don't think about functions as a function of a function of a function or whatever. You do mention that it's the same as
(Type, Type) -> Typelater, but honestly I would just use that notation throughout and ditchType -> Type -> Type. It's much easier to understand.
I'm keeping the syntax because it's unavoidable if you want to talk about functional topics, better to get accustomed to it. I agree it is difficult to understand at first, but given how pervasive this syntax is, that's not enough motivation for me
As I understand it,
Familyis just for one specific family of types? If so it would be clearer if it were called something like
Yes, just one specific family, I'll adjust the name, that's a good point
I'll be honest, I didn't actually understand your post until I wrote all this, but I finally understand what a functor and monad is (and how absolutely terrible all explanations of functor and monads are) so thank you!
Wow, when I wrote this I wasn't expecting people to actually understand Functor or Monad,it's nice that people are understanding it through this post!
Oh wow, thanks a lot! That's very helpful.
But people don't think about functions as a function of a function of a function or whatever
They absolutely do, once they get used to it.
Currying (the practice of rewriting functions of may arguments as nested functions of one argument each) ends up feeling perfectly natural after you use it for a while.
In fact, functional languages typically automatically curry every function you declare.
In fact, functional languages typically automatically curry every function you declare.
I'd argue that this is evidence that people don't think functions as if they were curried, else they would directly write a curried function. f x = \y -> (g x) y, anyone*?
Not that people never think of them as curried - when the situation is convenient, that is, when 'partially' applying the first n arguments is convenient, let's say mapf = map f instead of mapf x = map f x, where map f list applies a function f to each element of list - then, given some practice, people might think instead map turns f : Fn(A) -> B into map f : Fn(List<A>) -> List<B> (In Rust notation, or in Haskell f :: a -> b and map f :: [a] -> [b]) if the situation suits them. Else it feels forced - map_on_x f = map f x can be transformed on map_on_x = flip map x, sometimes in Haskell I try to write functions without naming their arguments - this is called *point-free style* - sometimes the result is nice, like the former, sometimes not so much, like the latter.
There are a few ´lift´ functions that do exactly that: take functions on, lets say, A, B, C ... Z, and turn them into functions on SomeT<A>, SomeT<B>, ..., SomeT<Z>. They could also be thought as functions that apply functions SomeT<*>. What way of thinking is best depends on the problem(or on the part of it) you are solving.
* There is a good example of a function written on this style, '.' - the composition operator: (f . g)(x) = f(g(x)).
One possible implementation is: f . g = \x -> f(g x). I think it transmits more the intent that this function composes functions, not that this function applies 2 functions on sequence(note that f . g x is actually f . (g x) due to precedence)
FYI, what you are doing is called defunctionalization on the type level, and it's a well-known technique. See Lightweight Higher-Kinded Polymorphism for a nice introduction.
Oh, cool! I'll link to that in part 2!
Someday, I will know enough to comprehend what is going on here, but it is not this day
This is how I feel about most of the Rust content I consume. I wish there was a comprehensive CS course in Rust.
I understand that reference
PART 1, there's more to come
So true 🤠HKT is something from other dimension.
But they are useful! Take a look at collections API, we could generalize over all the collections using HKT with one single line! I would really like HKT to happen in rust, but it seems that people decided not to include it.
I think because it is so complicated, and there wasn't time.
Rust already had a huge amount of complexity in the lifetime and borrowing systems. I can't imagine trying to explain this stuff to beginners.
It's also because a full implementation of GATs can be used to emulate HKTs (with more boilerplate), and GATs are a natural extension of the type system (we already have generics and associated types, we just need to merge them), while HKTs are significantly more abstract and complex