Expand description
Helper traits and types to work with some of the more advanced higher-order APIs.
§The what, the why and the how of Higher Kinded Types (HKTs)
- Feel free to also check up https://docs.rs/polonius-the-crab’s extensive
documentation, since it also has to deal with Higher-Kinded Types (even
though, in practice, it hides them under the
rugmacros 🙃)
§What are Higher-Kinded Types?
Click to show
A higher-kinded type is an actual / full / standalone type which is, itself, “generic”, or rather, to which we can further feed generic parameters (such as lifetime parameters or type parameters) to obtain further types.
- “is generic” / can be fed generic parameters to construct a type ❓
-
is a type in and of itself ❓
- For instance,
type Standalone = YourHktType;
has to compile.
- For instance,
One way to illustrate this difference, for instance, would be to consider:
use ::lending_iterator::higher_kinded_types::HKT;
type StringRefNaïve<'lt> = &'lt str;
// and
type StringRef = HKT!(<'lt> => &'lt str);
Both StringRefNaïve
and StringRef
can be fed a generic parameter (in this
instance, a lifetime parameter) so as to get or construct a type:
use ::lending_iterator::higher_kinded_types::{Feed, HKT};
const _: StringRefNaïve<'static> = "This is a `&'static str`";
const _: Feed<'static, StringRef> = "This is a `&'static str`";
- “is generic” / can be fed generic parameters to construct a type ✅
But what of:
- is a type in and of itself ❓
Well, while StringRef
is indeed a standalone type:
use ::lending_iterator::higher_kinded_types::HKT;
type StringRef = HKT!(<'lt> => &'lt str);
type Standalone = StringRef; // ✅
it turns out that StringRefNaïve
is not:
use ::lending_iterator::higher_kinded_types::HKT;
type StringRefNaïve<'lt> = &'lt str;
type Standalone = StringRefNaïve; // ❌ Error
This errors with:
error[E0106]: missing lifetime specifier
--> src/higher_kinded_types.rs:70:19
|
8 | type Standalone = StringRefNaïve; // ❌ Error
| ^^^^^^^^^^^^^^ expected named lifetime parameter
|
help: consider introducing a named lifetime parameter
|
8 | type Standalone<'a> = StringRefNaïve<'a>; // ❌ Error
| ++++ ~~~~~~~~~~~~~~~~~~
That is, in Rust a generic “type” is actually not a type. It’s just a path (grammar-wise), a name, to which we can feed the generic parameters so as to obtain types in return.
A HKT would be the proper solution to this: not only can such an “entity” be fed generic parameters (thence “acting like” a generic “type” above), it can also not be fed any parameters and still be a type. That is,
a HKT is an actual type which is generic / can be fed parameters.
Another definition, which will make more sense in the following section, is that HKTs come into play the moment we need “generic generics”.
§Why? What are Higher-Kinded Types for?
Click to show
§Type-HKTs
Click to show
Consider the following pseudo-code:
ⓘstruct StructOfArrays<ArrayKind : <T>> { array_of_i32s: ArrayKind<i32>, array_of_strings: ArrayKind<String>, } /** ```rust struct StructOfVecs { array_of_i32s: Vec<i32>, array_of_strings: Vec<String>, } ``` */ type StructOfVecs = StructOfArrays<Vec>; /** ```rust struct StructOfVecDeques { array_of_i32s: VecDeque<i32>, array_of_strings: VecDeque<String>, } ``` */ type StructOfVecDeques = StructOfArrays<VecDeque>;
Within this pseudo-code,
<ArrayKind>
is a generic parameter, but one which would be able to be fed a generic type parameter<T>
itself, so as to obtain each field type. So, we have a generic type parameter,<ArrayKind>
, which is expected to be, itself,<T>
-generic as well!Thence the term a “generic generic” (parameter).
And we could push that flexibility even further with idea of being able to produce and feed ad-hoc / on-demand “generic types” to these generic structs. Something along the lines of:
-
ⓘ
/** ```rust struct StructOfPairs { array_of_i32s: [i32; 2], array_of_strings: [String; 2], } ``` */ type StructOfPairs = StructOfArrays< HKT!(<T> => [T; 2]) >;
In some cases, that level of genericity can lead to very s(l)ick designs.
The example above was kind of contrived, but a more classic need would be to try and be generic over the thread-safety of a reference-counted pointer:
ⓘtype Arc = HKT!(<T> => ::std::sync::Arc<T>); type Rc = HKT!(<T> => ::std::rc::Rc<T>); type MyHandle<RefCountedPtr : <T>>( RefCounterPtr<Inner>, ); type MyHandleFast = MyHandle<Rc>; type MyHandleSync = MyHandle<Arc>;
-
§Lifetime HKTs
Click to hide
Another use case can be around lifetimes, when dealing with higher-order lifetimes (e.g., when exposing borrows of callee local variables to a caller-chosen generic parameter).
To illustrate, let’s consider the following example:
First the following type definition:
struct Person { name: String, surname: String, age: u8, }
and now consider an API being able to locally produce a borrow to a
Person
, (by locally it is meant that such borrow cannot escape the function call / is tied to the callee), which thus requires some form of callback:use ::core::cell::RefCell; fn for_each ( elems: &[RefCell<Person>], // this could be `FnMut`, but let's stick to `Fn` for the sake of simplicity. f: impl Fn(&Person), ) { elems .iter() .for_each(|refcell| { let local = refcell.borrow(); f(&*local); }) }
Now, let’s spice things a little. For starters, let’s consider that rather than a
Fn(&Person) /* -> () */
kind of callback, we’re gonna expect the user to map to one of its fields or dependent data so that we canDebug
it:use ::core::{ cell::RefCell, fmt::Debug, }; fn debug_each<R> ( elems: &[RefCell<Person>], f: impl Fn(&Person) -> R, ) where R : Debug, { elems .iter() .for_each(|refcell| { let local = refcell.borrow(); let field_to_debug = f(&*local); eprintln!("{:?}", field_to_debug); }) }
With this,
debug_each(elems, |person: &Person| -> u8 { person.age });
works Just Fine™.
But what of:
ⓘdebug_each(elems, |person: &Person| -> &str { person.name });
This will fail with a bunch of “conflicting lifetime requirements” error messages; we are now having to deal with higher-order lifetimes!
The gist of the issue is that here, we’d like to say that
R = &str
, right?But such statement is wave-handed and overlooking a crucial aspect here: what is the lifetime used in that
&str
?It turns out that we can’t really answer it: if we unsugar the
impl Fn
required signature, we have:impl Fn(&Person) -> R // is the same as: impl for<'local> Fn(&'local Person) -> R
and so we would have liked to pick
R = &'local str
.Let’s see the function signature that would have resulted from that:
fn debug_each<R /* = &'local str */> ( elems: &[RefCell<Person>], f: impl for<'local> Fn(&'local Person) -> R, ) where R : Debug,
Can you spot the issue?
'local
is not in scope when pickingR
!-
If you have followed the HKT introduction above, you may now start to see where I am going: we’d like to have a
R : <'lt>
HKT-y type (R = HKT!(<'lt> => &'lt str)
), so as to then use:ⓘf: impl for<'local> Fn(&'local Person) -> R<'local>
But you may consider this overly convoluted / overkill.
Indeed, there is a simpler way to make the signature compile: “just” slap a
&
in front of thatR
in the return type of the closure!fn debug_each<R : ?Sized /* = str */> ( elems: &'_ [RefCell<Person>], f: impl for<'local> Fn(&'local Person) -> &'local R, ) where R : Debug,
which, for better or for worse, can be further reduced down to:
fn debug_each<R : ?Sized /* = str */> ( elems: &[RefCell<Person>], f: impl Fn(&Person) -> &R, ) where R : Debug,
And when doing so, then yes,
|person: &Person| -> &str { &person.name }
will be a valid callback to feed to
debug_each
✅Except… that our previous:
ⓘdebug_each(elems, |person: &Person| -> u8 { person.age });
doesn’t compile anymore!
Easy —you may say— use
-> &u8
instead! (and&person.age
)And okay, that will work, but at this point we should start noticing that Rust is now dictating the rules, slowly narrowing down our intended API.
And this narrowing is no small thing. Indeed, now let’s consider that
Person
has some fancy getters:use ::std::borrow::Cow; pub struct Person { name: String, surname: String, age: u8, } impl Person { /// Case 1: getter that returns something _owned_. pub fn full_name (self: &'_ Person) -> String { format!( "{}{sep}{}", self.name, self.surname, sep = if self.name.is_empty() { "" } else { " " }, ) } /// Case 2: getter that returns a borrowing / dependent type which is /// not exactly a Rust reference. pub fn name_not_empty (self: &'_ Person) -> Cow<'_, str> { if self.name.is_empty() { format!("Mr/Ms {}", self.surname).into() } else { self.name.as_str().into() } } }
Now try to use either of
person.full_name()
orperson.name_not_empty()
with thisdebug_each()
API. You’ll see that “slap a&
on the return type” approach no longer works, you’ll get “borrow of dropped temporary” errors.Granted, you could duplicate
debug_each
into a-> R
API, and a-> &R
API (let’s call the latterdebug_each_ref
) —which incidentally is something that does happen in the Rust ecosystem. The other option is to forgo that-> &R
one, and require callers to.clone()
stuff to meet the-> R
requirement.😕
Neither of these things is satisfactory. We’d like to be generic over all the possible return types, whether they be borrowing/dependent or not, and whether they be exactly a Rust reference or a more complex type such as a
Cow
.Hence the need for HKTs, here.
The fully generic API would then thus be:
ⓘ//! In pseudo-code fn debug_each<R : <'lt>>( elems: &[RefCell<Person>], f: impl for<'local> Fn(&'local Person) -> R<'local>, ) where for<'lt> R<'lt> : Debug ,
A fully working example of this API using HKTs will be showcased below, once we’ve tackled replacing the pseudo-code with actual Rust.
-
§How? → Back to real Rust
Click to show
This, in real Rust, comes with three challenges:
-
Expressing that
ArrayKind : <T>
constraint. In other words, encoding the<T>
-ness property into a trait.trait HKT : /* magic */ { /* magic */ }
-
Applying / feeding a
<T>
type parameter to it to query the resulting type.Given our base idea of using a trait, this last aspect will involve querying an associated type; either through a generic helper trait, or with the associated type being, itself, generic:
-
With
generic_associated_types
:-
We could envision using:
ⓘtrait TypeHKT { type Assoc<T>; }
-
And then the querying of the type would be done with:
ⓘ<ArrayKind as TypeHKT>::Assoc<T>
for the
<T>
type-HKT case, and, similarly,for the
<'lt>
lifetime-HKT case. -
-
Without
generic_associated_types
:Alas, there is no way to express the
<T>
-over-types HKT-ness.But the good news is that the
<'lt>
-over-lifetimes HKT-ness can still be expressed, since lifetime GATs can be emulated in stable Rust:-
We define:
trait WithLifetime<'lt> { type Assoc; }
which encodes a single
'lt => Self::Assoc
mapping for theSelf
HKT. -
And then we alias:
trait HKT = for<'any> WithLifetime<'any>;
to encode the idea of having the aforementioned mapping exist
for
“all” /'any
possible choice of the'lt
.-
This
for
all / universal quantification of a trait bound is the magic that allows us to express the same as a GAT. In other words, GATs, can be viewed as “just” sugar for a universal trait quantification.Since
for<'lt>
is expressible in stable Rust, lifetime GATs can be emulated in stable Rust, and thus, lifetime-HKTs too, as showcased by this very post.But since
for<T>
is not yet a thing, neither type GATs nor type HKTs can be expressed in stable Rust 😔.
-
-
Querying the type is then done with:
<Type as WithLifetime<'lt>>::Assoc
-
-
-
Providing implementors or implementations of that trait:
-
neither
Vec
norVecDeque
are, alone, types. They’re “syntactical type paths” which can be fed a type parameter to then refer to one of theVec{,Deque}<T>
types.- See the previous sections for more info about this.
-
So we’ll need to define ad-hoc implementors of this genericity, as hinted by the aforementioned
HKT!(<T> => [T; 2])
example syntax.
So, while it would be possible to manually implement:
-
the
generic_associated_types
-based trait:impl {Type,}HKT for … { type Assoc<…> = …; }
, -
or even the without-
generic_associated_types
polyfill:impl<'lt> WithLifetime<'lt> for … { type Assoc = …; }
, the truth is that we don’t necessarily need to write all these implementations if we are able to somehow magically produce appropriate type implementors “on demand” (in an ad-hoc fashion).
And it turns out there is!
dyn
to the rescue!Indeed,
dyn Trait<…>
is a standalone / “on demand”-queryable type, which does implementTrait<…>
.From here, we come up with
dyn for<T> TypeHKT<Assoc<T> = …>
in the general case, anddyn for<'lt> WithLifetime<'lt, Assoc = …>
in the polyfilled case.§A convenience macro shorthand
Since remembering it all is hard, writing it in full, cumbersome, and reading it, noisy, this crate offers a convenience macro shorthand:
use ::lending_iterator::higher_kinded_types::HKT; type StringRef = HKT!(<'lt> => &'lt str); // or use elided lifetimes as "higher-order tokens": type StringRef2 = HKT!(&str); // <- same as `StringRef`!
More on this below.
-
§The HKT API of this crate
This crate needs HKTs to express some of the APIs involved with the iterator adaptors.
Given that 'next
lifetime involved in the key signature of a
LendingIterator
:
trait LendingIterator {
type Item<'next>
where
Self : 'next,
;
fn next<'next> (
self: &'next mut Self,
) -> Self::Item<'next>
;
}
it’s easy to guess that we’ll be dealing with <'next>
-one-lifetime-generic
kind of HKTs.
And luckily, this is the one expressible in stable Rust:
trait WithLifetime<'lt> {
type Assoc;
}
trait HKT = for<'any> WithLifetime<'any>;
§The three important things to remember when working with these HKT APIs
Click to hide
-
APIs use
T : HKT
to expressT : <'lt>
So, back to our aforementioned
debug_each
example API, thatR : <'lt>
bound would be expressed usingR : HKT
:fn debug_each<R : HKT> ( …
-
Given a
R : HKT
type, useFeed<'lt, R>
orApply!(R<'lt>)
to feed it a lifetime'lt
.fn debug_each<R : HKT> ( elems: &[RefCell<Person>], f: impl for<'local> Fn(&'local Person) -> Apply!(R<'local>), // or: f: impl Fn(&Person) -> Apply!(R<'_>), ) where for<'any> Apply!(R<'any>) : Debug ,
For those curious,
Apply!(R<'lt>)
is just sugar forFeed<'lt, R>
, which in turn is an alias for:<R as WithLifetime<'lt>>::T
-
And last but totally not least,
use
HKT!(<'lt> => Type…)
to define and provide an ad-hoc HKT / generic-lifetime-to-type association.debug_each::<HKT!(<'local> => &'local str)>( …
- 💡 The macro supports lifetime elision rules: you can directly feed a
type with elided lifetimes, as in
HKT!(Type<'_>)
, and the macro will automagically replace it withHKT!(<'a> => Type<'a>)
💡
// This works too! debug_each::<HKT!(&str)>( // or `HKT!(&'_ str)`. …
-
Note that nothing requires that these
HKT!
invocations be inlined in their turbofished sites; instead, you can easily define type aliases using them:type HKTRefStr = HKT!(<'lt> => &'lt str); debug_each::<HKTRefStr>( …
or even make the HKT, itself, be generic!
type HKTRef<T /* : ?Sized */> = HKT!(<'lt> => &'lt T); debug_each::<HKTRef<str>>( …
For those curious, the
HKT!
macro expands to adyn for<'lt> WithLifetime<'lt, T = …>
type, but wrapped in aPhantomData
-like data structure (dubbedHKT
as well), thanks to a blanket impl on them. This allows the macro to synthesizeSized
implementors ofHKT
, which thus allows for the callee signature to be alleviated thanks to it: it allows the callees / the called APIs to skip the noisy?Sized
unbounds on already heavy signatures). - 💡 The macro supports lifetime elision rules: you can directly feed a
type with elided lifetimes, as in
§Illustration: fully working code for the debug_each
example
Click to show
#![forbid(unsafe_code)]
use {
::core::{
cell::RefCell,
},
::lending_iterator::{
higher_kinded_types::{HKT, Apply},
},
};
struct Person {
name: String,
surname: String,
age: u8,
}
impl Person {
fn full_name (self: &'_ Person)
-> String
{
format!(
"{}{sep}{}",
self.name,
self.surname,
sep = if self.name.is_empty() { "" } else { " " },
)
}
fn name (self: &'_ Person)
-> ::std::borrow::Cow<'_, str>
{
if self.name.is_empty() {
format!("Mr/Ms {}", self.surname).into()
} else {
self.name.as_str().into()
}
}
}
fn debug_each<R : HKT, F> (
elems: &'_ [RefCell<Person>],
f: F,
)
where
F : Fn(&'_ Person) -> Apply!(R<'_>),
for<'any>
Apply!(R<'any>) : ::core::fmt::Debug
,
{
elems
.iter()
.for_each(|refcell: &'_ RefCell<Person>| {
let guard: ::core::cell::Ref<'_, Person> = refcell.borrow();
let person: &'_ Person = &*guard;
let to_debug: Apply!(R<'_>) = f(person);
eprintln!("{:?}", to_debug);
})
}
fn main ()
{
let array = [
RefCell::new(Person {
name: "".into(),
surname: "Globby".into(),
age: 0xff,
}),
];
let elems = &array[..];
// OK
debug_each::<HKT!(<'lt> => u8), _>(
elems,
|person: &'_ Person| -> u8 {
person.age
},
);
// OK
debug_each::<HKT!(String), _>( /* using the lifetime-elision syntax */
elems,
Person::full_name,
);
// OK
debug_each::<HKT!(::std::borrow::Cow<'_, str>), _>(
elems,
Person::name,
);
// OK as well!
debug_each::<HKT!(&str), _>(
elems,
|person: &Person| -> &str {
&person.surname
},
);
}
Macros§
Traits§
- HKT
- A trait to help express Higher Kinded Types.
- With
Lifetime HKT
’s internals.
Type Aliases§
- CanonicalHKT
- [eta-expansion] Projects an arbitrary
impl HKT
to itsHKT!
“canonical” (η-expanded) form. - Feed
- Given a
Type : HKT
,Feed<'lt, Type>
“feeds” / applies the<'lt>
toType
. - HKTItem
- “Lift” and convert an
impl LendingIterator
into animpl HKT
. - HKTRef
- Pervasive
HKT!
choice:HKT!<&T>
- HKTRef
Mut - Pervasive
HKT!
choice:HKT!<&mut T>