Does rust really need higher kinded types?

[shelby3]

@keean

A number of threads (including the most desired features thread) have suggested that Rust needs higher-kinded-types.

Note @keean means higher-ranked types, not higher-kinded types (HKT):

@shelby3

I think you mean higher-ranked, not higher-kinded (refer to the quoted linked Scala example):

@keean knows this, but for other readers HKT applies to the design case where(1) the return type of trait method needs to match the Self type and where the trait has type parameter(s) (e.g. associated type parametrized by lifetime which is a type parameter of the Self type for an Iterator factory method):

@shelby3

If I am not mistaken, a higher-kinded type is parametrization of a type parameter. The reason your first example is higher-kinded is because you require that the type parameter Iterator's lower bound Self::Iterator<'a> is a member of the implementating type Self. Thus you have parametrized the type parameter Self with the type parameter Iterator. If you had not required that Iterator to have a lower bound incorporating Self, then your example would not be higher-kinded.

@shelby3

Let's review why functors require higher-kinded types. Seems you are requiring something like the following (apologies if the Rust syntax isn't correct):

trait Functor {
type T;
fn map<A>(&self, T -> A) -> Self<T=A>;
}

We might contemplate to do instead the following which is not higher-kinded:

trait Functor {
type T;
fn map<A>(&self, T -> A) -> &Functor<T=A>;
}

So in other words, the trait object would maintain the runtime knowledge about what the implementing Self type is, which is not checked at compile time.

However, you are correct on this point, because the type signature of the alternative is not constrained to a functor.map operation, because there is no requirement that the return value have the same Self type. For example, the implementation could employ monoid.append to return a Functor which has a different Self type, e.g. convert from a Vec<T> to List<A>, which would violate the invariants of the category theory for a functor.

So thus you have pointed out an example of where we must have higher-kinded types.

I think we have shown that higher-kinded types are required when either we must restrict a trait type to a parametrization of the Self type for reasons of conformance to invariants (e.g. category theory for functors) or because we wish to forsake some generality in order to get more optimization (e.g. not using a trait object for an iterator, but where it is possible to get similar optimization using functors but these require higher-kinded types also and we might gain some other higher-level functional composition abstraction and control over resource management to avoid the low-level imperative approach).

---

(1) Note HKT generally apply in any case where we parametrize a type parameter of the trait (i.e. higher order constructors), not just when Self (which btw is a type parameter) is parametrized and used as a return type, but this latter case is probably the most prolific use case of HKT.

In Scala which has HKT, we can clearly see Self is a type parameter:

trait Super[Self <: Super]

And can be HKT:

trait Super[T, Self[T] <: Super[T, Self]]