Higher Kinded Types in Rust

I don’t know if I can do an example in a common enough syntax to make sense. However, the general/basic example for higher kinded types is usually a Collection<T> vs a List<T>.

The List take some type T (i.e. int, float, char) and is a list of ‘objects’ of that type. Every ‘object in the list is an int.

A Collection<T> is a collection of some type <T<T2>> (i.e. list<T>, option<U>, vector<V>). This allows for the collection to be composed of ‘objects’ whose types are each some List<T> where each objects T can be different. So a Collection<List<T>> could be a list of [List<int>, List<float>, List<char>].

I think the jargony statement is that higher kinded types allow for a type to abstract over types which take another type as a constructor.

From my perspective the rationale for higher kinded type is usually the drive/goal of having as high a ceiling for abstraction as possible and create ‘reusable’ and generic code over and above what is available without higher kinded types.

Let's say you want to write a generic function to convert from a container type to another container type:

    linked_list<int> l;
    vector v = to_container(l);

In C++ this would be:

    template<template<class...> class ResultT, range Range, class T = range_value_t<Range> >
    ResultT<T> to_container(Range range) {
       return ResultT<T>(begin(range), end(range));
    }

    list<int> x = ...;
    vector y = to_container<vector>(x);

Because of the lack of type inference (only a simple form of type deduction is available in C++)[1], we have to specify the kind of container we want in the call to to_container. We do not have to specify the value type though (int in this case), so the ResultT parameter of to_container is an HKT. Range_value_t is a type query to get the value_type of the range. It is used to initialize a default template parameter purely for syntactical convenience.

This is C++ of course so things are always a bit more complex. In particular a template template parameter is not really a type which makes is harder to manipulate consistently.

More advanced metaprogramming libraries prefer to use types with associated templated types instead, which are another form of HKT, but it is not needed for this case.

There are also ways around having to specify vector in the call to to_container using a proxy result type and a templated conversion operator, but it is again overkill in this case.

Finally note that C++ templates are by default untyped: only instantiations are type checked. We use concepts for the range parameter that at least allows type checking of the range parameter at the call site without full instantiation, but as far as I can tell there are still no higher kinded concepts.

I believe that Rust doesn't have HKTs yet exactly because higher kinded concepts (called traits in rust) are hard to define.

[1] whether languages with proper type inference can deduce HTKs is beyond my pay grade, but I assume they can.

With class/object generics, you are abstracting over the type the class is operating on, so you can have a List<Int> or List<String>. The class can define a single implementation on all those types, and functions using that class can be written that also operate on any List instance (List<T>).

If you have a function `f(A) -> B` (e.g. converting a String to an Integer), you can define a map operation that works on List<A> and returns a List<B> by applying f to each item in List<A>. This map operation is useful for other objects (Optional, Set, Array, etc.). It is also the building block for other functions.

Higher Kinded Types allow you to say you have some type F<T>, where F is a type (List, Array, etc.) that can operate on any instance of T in a way that you can vary T without varying F. You could then define map like:

    interface Mappable<A, F<A>> {
        fun map<B>(f: (A) -> B): F<B>
    }

    class List<T> : Mappable<T, List<T>> {
        fun map<B>(f: (A) -> B): List<B> { ... }
    }

What category theory does is define a common language for these operations, and combined types -- which is where you get terms like Monad from. From a programming perspective, this is just an interface that implements several other interfaces, provides a set of methods an implementation must implement, and a set of methods the implementation gets "for free". -- This is similar to implementing Iterable, List, or other collection interfaces and getting a bunch of functionality for free.

> What problem would higher kinded types solve in Rust?

You don't have a way to say in Rust 'this functions works on types similar to an 'Option<T>' for all types T. Or 'this functions works on types similar to a 'LinkedList<T>' for all types T. Which actually is more or less the same, we can therefore name both 'Option' and 'LinkedList' for example, well, 'Mona'.

ROFL, oh yes this is so much better and the syntax so much clearer than C++. ;)

Hum... Even though C++ can do HKT with templates, it's not a convenient feature of the language.

C++ is really not the language that comes to mind when somebody talks abut HKT.

Hard/confusing for user programmers, or for language designers? I don't think the concept being tricky for users is what is preventing adoption of HKTs. The &|x| hints at some of the reasons why implementing HKTs in Rust is tricky (not impossible). They are naturally very abstract, and if a structure is to be compiled in Rust, it (and its lifetime) needs to be reified. That is no small feat. See also: the difficulty with callbacks/anonymous closures in Rust.

You could add lazy evaluation and call your language Curry.

This feels unnecessarily snarky. If you wanna write in Haskell, use Haskell. Rust is a different beastie with different use cases. There's no reason why any language shouldn't benefit from a powerful type system if they can manage it.