Higher-kinded types in Rust

Question

Also posted on Reddit.

As a small personal exercise, I'm trying to implement a notion of higher-kinded types in Rust using type-level defunctionalisation based on the "Lightweight higher-kinded polymorphism" paper.

Here's some of the work I've done so far:

// Type-level application.
// \* -> *
trait Kind<A> {
 type Output;
}
type Apply<Brand, A> = <Brand as Kind<A>>::Output;
// Type-level injection.
// \* -> *
trait Inject<Brand> {
 type A;
 fn inject(self) -> Apply<Brand, Self::A>
 where
 Brand: Kind<Self::A>;
}
// Type-level projection.
// \* -> *
trait Project<Brand: Kind<A>, A> {
 type Concrete;
 fn project(self) -> Self::Concrete;
}
// Typeclasses.
trait Sequence<Brand: Kind<A>, A> {
 // forall f a b. Sequence f => f (a -> b) -> f a -> f b
 fn sequence<F, B>(ff: Apply<Brand, F>) -> impl Fn(Apply<Brand, A>) -> Apply<Brand, B>
 where
 F: Fn(A) -> B + Copy,
 Brand: Kind<F> + Kind<B>;
}
// forall f a b. Sequence f => f (a -> b) -> f a -> f b
fn sequence<Brand, F, A, B>(ff: Apply<Brand, F>) -> impl Fn(Apply<Brand, A>) -> Apply<Brand, B>
where
 Brand: Kind<F> + Kind<A> + Kind<B>,
 F: Fn(A) -> B + Copy,
 Apply<Brand, A>: Sequence<Brand, A>,
{
 let f = <Apply<Brand, A>>::sequence::<F, B>(ff);
 move |fa| f(fa)
}
// Types.
#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
enum Maybe<A> {
 Just(A),
 #[default]
 Nothing,
}
struct MaybeBrand;
impl<A> Kind<A> for MaybeBrand {
 type Output = Maybe<A>;
}
impl<A> Inject<MaybeBrand> for Maybe<A> {
 type A = A;
 fn inject(self) -> Apply<MaybeBrand, A> {
 self
 }
}
impl<A> Project<MaybeBrand, A> for <MaybeBrand as Kind<A>>::Output {
 type Concrete = Maybe<A>;
 fn project(self) -> Self::Concrete {
 self
 }
}
impl<A> Sequence<MaybeBrand, A> for Maybe<A> {
 fn sequence<F, B>(
 ff: Apply<MaybeBrand, F>,
 ) -> impl Fn(Apply<MaybeBrand, A>) -> Apply<MaybeBrand, B>
 where
 F: Fn(A) -> B + Copy,
 MaybeBrand: Kind<F> + Kind<B>,
 {
 let ff: Maybe<F> = ff.project();
 move |fa| {
 (match (&ff, fa.project()) {
 (Maybe::Just(f), Maybe::Just(a)) => Maybe::Just(f(a)),
 _ => Maybe::Nothing,
 })
 .inject()
 }
 }
}
// Main entry.
fn main() {
 println!(
 "{:?}",
 sequence::<MaybeBrand, _, _, _>(Maybe::Just(|x| x + 1))(Maybe::Just(0))
 );
}

My questions are:

1. Is it possible to make the Inject and Project traits be constraints of the associated Output type of Kind, while ensuring that Kind is still implementable?

I tried using the following defintion for Kind instead:

trait Kind<A>: Sized {
 type Output: Inject<Self> + Project<Self, A>;
}

But I'm unsure if it's correct and couldn't figure out how to implement it for Maybe.

2. Is it possible to generically call sequence and have Rust's type checker/trait solver infer the types and required instances automatically instead of having to manually annotate the Brand required, as I've done above in the main function, where I manually annotated using MaybeBrand? Why couldn't Rust automatically infer that it should use MaybeBrand in that case?

3. What's a good way to make the free function, sequence, also be able to handle kinds of higher arities? For instance, how would I also make it work with a version of Sequence for kinds of arity 2 (which would be used for the Either/Result type):

// \* -> * -> *
trait Kind2<A, B> {
 type Output;
}
// \* -> * -> *
type Apply2<Brand, A, B> = <Brand as Kind2<A, B>>::Output;
trait Sequence2<Brand: Kind2<A, B>, A, B> {
 fn sequence<F, C>(ff: Apply2<Brand, A, F>) -> impl Fn(Apply2<Brand, A, B>) -> Apply2<Brand, A, C>
 where
 F: Fn(B) -> C + Copy,
 Brand: Kind2<A, F> + Kind2<A, C>;
}

Could I possibly implement sequence as a macro instead?

Answer 1

I think I misunderstood the paper before. After going through it again, I now think the typeclass is supposed to be implemented by the brand, and not directly by the type, like I initially thought.

I've since reimplemented my code above into the following version:

trait Kind<A> {
 type Output;
}
type Apply<Brand, A> = <Brand as Kind<A>>::Output;
trait Sequence {
 fn sequence<F, A, B>(ff: Apply<Self, F>) -> impl Fn(Apply<Self, A>) -> Apply<Self, B>
 where
 F: Fn(A) -> B + Copy,
 Self: Kind<F> + Kind<A> + Kind<B>;
}
fn sequence<Brand, F, A, B>(ff: Apply<Brand, F>) -> impl Fn(Apply<Brand, A>) -> Apply<Brand, B>
where
 F: Fn(A) -> B + Copy,
 Brand: Kind<F> + Kind<A> + Kind<B> + Sequence,
{
 let f = Brand::sequence::<F, A, B>(ff);
 move |fa| f(fa)
}
#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
enum Maybe<A> {
 Just(A),
 #[default]
 Nothing,
}
struct MaybeBrand;
impl<A> Kind<A> for MaybeBrand {
 type Output = Maybe<A>;
}
impl Sequence for MaybeBrand {
 fn sequence<F, A, B>(ff: Apply<Self, F>) -> impl Fn(Apply<Self, A>) -> Apply<Self, B>
 where
 F: Fn(A) -> B + Copy,
 {
 move |fa| match (ff, fa) {
 (Maybe::Just(f), Maybe::Just(a)) => Maybe::Just(f(a)),
 _ => Maybe::Nothing,
 }
 }
}
fn main() {
 println!(
 "{:?}",
 sequence::<MaybeBrand, _, _, _>(Maybe::Just(|x| x + 1))(Maybe::Just(0))
 );
}

Doing it this way actually allows the typeclasses not to require generic type parameters anymore; these are now changed to be generic type parameters of the required methods instead.

This also seems to address my first question, as this new implementation no longer seems to require the inject and project functions. (削除) However, I still haven't figured out the answers to my second and third questions. (削除ここまで)

I think I've figured out some answers for my third question and partially for my second. Namely, by looking closer at how Haskell implements Functor for Either, I realised that they've implemented it for the partially applied type, Either a, and not Either itself.

In other words, in their case, Either a already has its Left constructor applied, so its type has kind arity 1, since it's still expecting another value for its Right constructor for it to be fully reified. With that realisation, I've ended up creating a brand for Either that has a type parameter, to represent the partially applied type of Either a, as follows:

pub trait Kind<A> {
 type Output;
}
pub type Apply<Brand, A> = <Brand as Kind<A>>::Output;
pub trait Functor {
 /// forall f a b. Functor f => (a -> b) -> f a -> f b
 fn map<F, A, B>(f: F) -> impl Fn(Apply<Self, A>) -> Apply<Self, B>
 where
 F: Fn(A) -> B + Copy,
 Self: Kind<A> + Kind<B>;
}
/// forall f a b. Functor f => (a -> b) -> f a -> f b
pub fn map<Brand, F, A, B>(f: F) -> impl Fn(Apply<Brand, A>) -> Apply<Brand, B>
where
 F: Fn(A) -> B + Copy,
 Brand: Kind<A> + Kind<B> + Functor,
{
 move |fa| Brand::map::<F, A, B>(f)(fa)
}
pub trait Sequence {
 /// forall f a b. Sequence f => f (a -> b) -> f a -> f b
 fn sequence<F, A, B>(ff: Apply<Self, F>) -> impl Fn(Apply<Self, A>) -> Apply<Self, B>
 where
 F: Fn(A) -> B + Copy,
 Self: Kind<F> + Kind<A> + Kind<B>;
}
/// forall f a b. Sequence f => f (a -> b) -> f a -> f b
pub fn sequence<Brand, F, A, B>(ff: Apply<Brand, F>) -> impl Fn(Apply<Brand, A>) -> Apply<Brand, B>
where
 Brand: Kind<F> + Kind<A> + Kind<B> + Sequence,
 F: Fn(A) -> B + Copy,
{
 let f = Brand::sequence::<F, A, B>(ff);
 move |fa| f(fa)
}
#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub enum Maybe<A> {
 Just(A),
 #[default]
 Nothing,
}
pub struct MaybeBrand;
impl<A> Kind<A> for MaybeBrand {
 type Output = Maybe<A>;
}
impl Sequence for MaybeBrand {
 fn sequence<F, A, B>(ff: Apply<Self, F>) -> impl Fn(Apply<Self, A>) -> Apply<Self, B>
 where
 F: Fn(A) -> B + Copy,
 {
 move |fa| match (ff, fa) {
 (Maybe::Just(f), Maybe::Just(a)) => Maybe::Just(f(a)),
 _ => Maybe::Nothing,
 }
 }
}
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub enum Either<A, B> {
 Left(A),
 Right(B),
}
pub struct EitherAppliedLeftBrand<E>(E);
impl<E, A> Kind<A> for EitherAppliedLeftBrand<E> {
 type Output = Either<E, A>;
}
impl<E> Functor for EitherAppliedLeftBrand<E> {
 fn map<F, A, B>(f: F) -> impl Fn(Apply<Self, A>) -> Apply<Self, B>
 where
 F: Fn(A) -> B + Copy,
 {
 move |fa| match fa {
 Either::Left(e) => Either::Left(e),
 Either::Right(a) => Either::Right(f(a)),
 }
 }
}
impl<E> Sequence for EitherAppliedLeftBrand<E>
where
 E: Clone,
{
 fn sequence<F, A, B>(ff: Apply<Self, F>) -> impl Fn(Apply<Self, A>) -> Apply<Self, B>
 where
 F: Fn(A) -> B + Copy,
 {
 move |fa| match (&ff, &fa) {
 (Either::Left(e), _) => Either::Left(e.clone()),
 (Either::Right(f), _) => map::<EitherAppliedLeftBrand<_>, _, _, _>(f)(fa),
 }
 }
}
fn main() {
 println!(
 "{:?}",
 sequence::<MaybeBrand, _, _, _>(Maybe::Just(|x| x + 1))(Maybe::Just(0))
 );
 println!(
 "{:?}",
 sequence::<EitherAppliedLeftBrand<_>, _, _, _>(Either::Right::<(), _>(|x| x + 1))(
 Either::Right::<(), _>(0)
 )
 );
}

This addresses my third question, since I can now use the free functions, map and sequence, for both Maybe and Either types, by simply specifying which brand to specialise the functions to, since both MaybeBrand and EitherAppliedLeftBrand have kind arity 1.

Regarding question 2, I'm leaning towards the answer being that it's not (currently) possible for Rust compiler to infer what type to use for the Brand generic type parameter of the free functions, since I can imagine that it's possible to create multiple brands for a type, in which case there'd be multiple possible type arguments that could be used.

However, since I only have one brand for each of Maybe and Either at the moment, I would've expected Rust's compiler to be able to infer which one to use by process of elimination. Perhaps this could be a feature we might see built in to the type-checker/trait-solver in the future, or perhaps I'm completely off-base with my theory, in which case, please let me know. I'd love to get some concrete answers about the matter. For now though, I think I can consider my questions adequately settled.

For posterity, I'm leaving a link to my project's repo here. There, you can see the other typeclasses and types that I've implemented so far.