Is there an intrinsic reason explaining why Rust does not have higher-kinded-types?

Question

Rust does not have higher-kinded-types. For example, functor (and thus monad) cannot be written in Rust. I would like to know if there is a deep reason explaining this and why.

For instance, reason that I can understand can be that there is no zero-cost abstraction making HKT possible. Or type inference is significantly more difficult. And of course, I also looking for an explaination showing me why this is a real limitation.

If the anwer was already given somewhere else, could you give me the link?

Amarillis

Answer 1

Time & Priority.

The absence of Higher Kinded Types is not a design decision, per se. It is intended that Rust will have some form of it, with the more popular candidate being Generic Associated Types (2017) at the moment.

Implementing those take time, though, and has not been judged a priority compared to other features. For example, async/await was prioritized over HKTs, and const generics also seem to be prioritized.

---

For example, functor (and thus monad) cannot be written in Rust.

Actually, they can, although it's a bit unwieldy.

See Edmund's Smith lovely hack which he posted on https://www.reddit.com/r/rust/comments/cajn09/new_method_for_emulating_higherkinded_types_in/:

trait Unplug {
    type F; //The representation type of the higher-kinded type
    type A; //The parameter type
}

trait Plug<A> {
    type result_t;
}

pub  struct  Concrete<M: Unplug + Plug<A>,A> {
    pub unwrap: <M as Plug<A>>::result_t
}

impl<M: Unplug + Plug<A>, A> Concrete<M,A> {
    fn of<MA: Unplug<F=M, A=A> + Plug<A>>(x: MA) -> Self
        where M: Plug<A, result_t = MA>
    {
        Concrete { unwrap: x }
    }
}

With which they implement a Functor trait:

pub trait Functor: Unplug + Plug<<Self as Unplug>::A> {
    fn map<B, F>(f: F, s: Self) -> <Self as Plug<B>>::result_t
        where
            Self: Plug<B>,
            F: FnMut(<Self as Unplug>::A) -> B
        ;
}

//  Example impl for a represented Vec
impl<A> Functor for Concrete<Vec<forall_t>, A> {
    //  remember, Self ~ (Vec<_>, A) ~ "f a"
    fn map<B, F>(f: F, s: Self) -> <Self as Plug<B>>::result_t
        where
            F: FnMut(<Self as Unplug>::A) -> B 
    {        
        Concrete::of(s.unwrap.into_iter().map(f).collect())
    }
}

And from then on build Applicative and Monad:

pub trait Applicative: Functor {
    fn pure(s: <Self as Unplug>::A) -> Self;

    fn app<B, F>(
        f: <Self as Plug<F>>::result_t, //M<F>
        s: Self                         //M<A>
    ) -> <Self as Plug<B>>::result_t   //M<B>
    where
        F: FnMut(<Self as Unplug>::A) -> B + Clone,
        Self: Plug<F> + Plug<B> + Unplug,
        <Self as Plug<F>>::result_t:
            Unplug<F=<Self as Unplug>::F, A=F> +
            Plug<F> +
            Clone,
        <Self as Unplug>::F: Plug<F>
    ;
}

pub trait Monad : Applicative {
    fn bind<F,B>(f: F, s: Self) -> <Self as Plug<B>>::result_t
    where
        Self: Plug<F>+Plug<B>,
        F: FnMut(<Self as Unplug>::A) ->
            <Self as Plug<B>>::result_t + Clone
        ;
}

I did say it was a bit unwieldy...

Fijian

Ok thank you very much for your response! I'm just wondering why using something triky like GAT for HKT instead of using Haskell simple forme. But I'm perhaps missing something... – Amarillis

@Amarillis I think you're missing that you can't "just" add Haskell-like HKTs to Rust -- you need to (1) define how the feature interacts with the rest of the language and (2) actually implement it. GATs are a small, orthogonal feature that has already been fully defined and is being implemented. This blog series (in 4 parts) describes in detail the relationship between GATs (referred to as ATCs at the time) and HKTs. – Kirghiz

Part 3 in particular highlights some differences between Rust and Haskell that would make it awkward to bolt (parts of) Haskell's system on to Rust. – Kirghiz

Yes I completely agree with you : regarding the current state of rust, adding some kind of feature may be tricky.What I just wanted to know was if there were a reason why the original design did not include this feature from the beginning. In fact i'm just interesting in knowing the requirement design of rust which made rust look like today's rust. But your links may help me to know that, I'm going to read it. Thank you! – Amarillis

How can I keep track of what is planned to be added to Rust eventually? – Roughish

@user1857492: By keeping up with the discussions, and notably RFCs, I would say. It's pretty much similar to Python / Java / C++ in that regard. – Fijian