Seamless Higher-Kinded Types in Rust

This is actual working code:

pub trait Functor<A> : HKT1 {
    fn map<B, F: FnMut(A) -> B>(self, f: F) -> Self::With<B>;
}

pub trait Applicative<A> : Functor<A> {
    fn pure(a: A) -> Self;
    fn apply<B, F: FnMut(A) -> B>(self, ff: Self::With<F>) -> Self::With<B>;
}

pub trait Monad<A> : Applicative<A> {
    fn ret(a: A) -> Self;
    fn flatmap<B, F: FnMut(A) -> Self::With<B>>(self, f: F) -> Self::With<B>;
}

Here are some implementations for Vec:

implHKT1!(Vec);         // the magic part!

impl<A> Functor<A> for Vec<A> {
    fn map<B, F: FnMut(A) -> B>(self, f: F) -> Self::With<B> {
        self.into_iter().map(f).collect()
    }
}

impl<A> Applicative<A> for Vec<A> {
    fn pure(a: A) -> Self {
        vec![a]
    }

    fn apply<B, F: FnMut(A) -> B>(self, ff: Self::With<F>) -> Self::With<B> {
        ff.into_iter().zip(self.into_iter()).map(
            |(mut f, x)| f(x)
        ).collect()
    }
}

impl<A> Monad<A> for Vec<A> {
    fn ret(a: A) -> Self {
        vec![a]
    }

    fn flatmap<B, F: FnMut(A) -> Self::With<B>>(self, mut f: F) -> Self::With<B> {
        self.into_iter().flat_map(|x| f(x).into_iter()).collect()
    }
}

Let's try our flatmap:

assert_eq!(
    vec![1, 2, 3].flatmap(|x| vec![x, x*x, x*x*x]),
    vec![1, 1, 1, 2, 4, 8, 3, 9, 27]
);

Here's an example with 2 type parameters:

trait Mixuppable<T1, U1> : HKT2 {
    fn mixup<T2, U2>(self, other: Self::With<T2, U2>) -> Self::With<T1, U2>;
}

struct Point<T, U> {
    x: T,
    y: U
}

struct _NotPoint<T, U> {
    a: T,
    b: U
}

implHKT2!(Point);

impl<T1, U1> Mixuppable<T1, U1> for Point<T1, U1> {
    // // ERROR: expected struct `Point`, found struct `_NotPoint`
    // fn mixup<T2, U2>(self, other: Point<T2, U2>) -> _NotPoint<T1, U2> {
    //     todo!()
    // }
    
    fn mixup<T2, U2>(self, other: Point<T2, U2>) -> Point<T1, U2> {
        Point { x: self.x, y: other.y }
    }
}

Can we still claim that Rust doesn't support HKTs, in practice?

Under the hood [obsolete]

The implementation of implHKT1 is trivial:

pub unsafe trait HKT1 {
    type With<W1>;
}

#[macro_export]
macro_rules! implHKT1 {
    ($TypeIdent:ident) => {
        unsafe impl<T1> HKT1 for $TypeIdent<T1> {
            type With<S1> = $TypeIdent<S1>;
        }
    };
}

Notice the use of the unsafe keyword.

The unsafe keyword indicates that HKT1 has invariants that the compiler can't verify, which is exactly what's happening here!

If users try to implement HKT1 on their own, they will get an error. Then it's their responsibility to do the right thing and use the macro instead of just marking their implementation as unsafe.

A little detail: to avoid redefinitions, I call the macros for external types (e.g. Vec and Option) once and for all in ext_hkts_impls.rs.

Under the hood v2

It seems Rust community hates my use of unsafe since I'm extending its meaning beyond what they deem acceptable. I think the pros outweighed the cons, but, luckily, there's a better solution (and possibly others) that avoids the unsafe hack and it's even safer:

pub trait HKT1 {
    type HKTInner1;
    type With<W1>:
        HKT1<HKTInner1 = W1> +
        HKT1<With<Self::HKTInner1> = Self> +
        HKT1<With<W1> = Self::With<W1>>;
}

This was suggested by u/Chadshinshin32 in this comment on reddit.

Let's consider a more general case and let's try to show (informally) its correctness:

pub trait HKT2 {
    type HKTInner1;
    type HKTInner2;
    type With<W1, W2>:
        HKT2<HKTInner1 = W1, HKTInner2 = W2> +
        HKT2<With<Self::HKTInner1, Self::HKTInner2> = Self> +
        HKT2<With<W1, W2> = Self::With<W1, W2>>;
}

Let's start with no bounds on With and then add them back one at a time, updating our as-general-as-possible implementation so that it doesn't violate them:

pub trait HKT2 {
    type HKTInner1;
    type HKTInner2;
    type With<W1, W2>:
        //    HKT2<HKTInner1 = W1, HKTInner2 = W2>
        //  + HKT2<With<Self::HKTInner1, Self::HKTInner2> = Self>
        //  + HKT2<With<W1, W2> = Self::With<W1, W2>>
         ;
}

struct A;
struct B;
struct C;

impl<T, U> HKT2 for OK1<T, U> {
    type HKTInner1 = A;
    type HKTInner2 = B;
    type With<W1, W2> = C;
}

Now let's add back the first bound:

pub trait HKT2 {
    type HKTInner1;
    type HKTInner2;
    type With<W1, W2>:
           HKT2<HKTInner1 = W1, HKTInner2 = W2>
        //  + HKT2<With<Self::HKTInner1, Self::HKTInner2> = Self>
        //  + HKT2<With<W1, W2> = Self::With<W1, W2>>
         ;
}

struct A;
struct B;
struct OK1<T, U> { x: (T, U) }
struct OK2<T, U> { x: (T, U) }
struct OK3<T, U> { x: (T, U) }
struct OK4<T, U> { x: (T, U) }

impl<T, U> HKT2 for OK1<T, U> {
    type HKTInner1 = A;
    type HKTInner2 = B;
    type With<W1, W2> = OK2<W1, W2>;
}

impl<T, U> HKT2 for OK2<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK3<W1, W2>;
}

impl<T, U> HKT2 for OK3<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK4<W1, W2>;
}

impl<T, U> HKT2 for OK4<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK3<W1, W2>;
}

(In what follows, I'll say OKx as short for "the implementation of HKT2 for OKx".)

We can create as long a WITH-chain as we want, but we need to "close" it at a certain point. I closed it by making OK4 refer back to OK3. Notice how OK1 is the only HKT2 still with arbitrary HKTInner1 and HKTInner2.

Now let's consider the second bound. Let's focus on OK1. The bound requires that OK2<W1, W2> is an HKT2<With<A, B> = Self>, i.e. that OK2<W1, W2>::With<A, B> = OK1<T, U>, which implies that OK2 must refer back to OK1, and that A = T, B = U:

pub trait HKT2 {
    type HKTInner1;
    type HKTInner2;
    type With<W1, W2>:
           HKT2<HKTInner1 = W1, HKTInner2 = W2>
         + HKT2<With<Self::HKTInner1, Self::HKTInner2> = Self>
        //  + HKT2<With<W1, W2> = Self::With<W1, W2>>
         ;
}

struct OK1<T, U> { x: (T, U) }
struct OK2<T, U> { x: (T, U) }

impl<T, U> HKT2 for OK1<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK2<W1, W2>;
}

impl<T, U> HKT2 for OK2<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK1<W1, W2>;
}

Focusing on OK1, we can see that the last bound requires that OK2<W1, W2>::With<W1, W2> = OK2<W1, W2>, which means that OK2 must refer to OK2 instead of OK1:

pub trait HKT2 {
    type HKTInner1;
    type HKTInner2;
    type With<W1, W2>:
           HKT2<HKTInner1 = W1, HKTInner2 = W2>
         + HKT2<With<Self::HKTInner1, Self::HKTInner2> = Self>
         + HKT2<With<W1, W2> = Self::With<W1, W2>>
         ;
}

struct OK1<T, U> { x: (T, U) }
struct OK2<T, U> { x: (T, U) }

impl<T, U> HKT2 for OK1<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK2<W1, W2>;
}

impl<T, U> HKT2 for OK2<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK2<W1, W2>;        // changed from OK1 to OK2
}

We can't do this, though, as this violates the second bound. Basically, we have:

• (Bound 2) OK2<W1, W2>::With<T, U> = OK1<T, U>
• (Bound 3) OK2<W1, W2>::With<W1, W2> = OK2<W1, W2>

For all T and U, by choosing W1 = T and W2 = U, we get OK1<T, U> = OK2<T, U>, that is, OK1 = OK2:

pub trait HKT2 {
    type HKTInner1;
    type HKTInner2;
    type With<W1, W2>:
           HKT2<HKTInner1 = W1, HKTInner2 = W2>
         + HKT2<With<Self::HKTInner1, Self::HKTInner2> = Self>
         + HKT2<With<W1, W2> = Self::With<W1, W2>>
         ;
}

struct OK1<T, U> { x: (T, U) }

impl<T, U> HKT2 for OK1<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK1<W1, W2>;
}

This is the only allowed implementation!

This is just a POC, so feel free to add derive macros, modify names to avoid name collisions, and so on... I've just read The Book and been programming in Rust for a couple of days (to code this POC!), so I'm not familiar with Rust ecosystem and its conventions.

That's all! Happy coding!